Given a string composed of parentheses characters '(' and ')' where the number of opening and closing parentheses is equal, determine the minimum number of character swaps required to make the string balanced.

A balanced parentheses string has matching opening and closing parentheses in the correct order. For example, '()' and '()()' are balanced, while '()' and '()(' are not.

Problem

Complete the function minSwaps in the editor with the following parameter(s): string s: a string of parentheses

Returns: int: the minimum number of swaps required to make a balanced parentheses string.

Constraints

• 2 ≤ length of s ≤ 2*10^5
• The length of s is even

Input

A string s of parentheses

Output

The minimum number of swaps required to make the string balanced