Problem Statement

Given is a string S consisting of (, ), o, and x.
You can swap two adjacent characters in S any number of times.
Find the minimum number of swaps needed to satisfy the following condition.

• Let us make a string S' consisting of ( and ) by replacing every occurrence of o with () and every occurrence of x with )( in S.
  Then, S' is a balanced parenthesis string.

Definition of a balanced parenthesis string

A balanced parenthesis string is a string that is one of the following:

• an empty string;
• a string that is a concatenation of s, t in this order, where s and t are some non-empty balanced parenthesis strings;
• a string that is a concatenation of (, s, ) in this order, where s is some balanced parenthesis string.

Under the Constraints of this problem, it is always possible to achieve the objective.

Input

Input is given from Standard Input in the following format:
S

Output

Print the answer.

Constraints

• S is a string consisting of (, ), o, and x.
• S contains the same non-zero number of (s and )s.
• $|S| \leq 8000$

Sample Input 1

)x(

Sample Output 1

3

We should do as follows: )x( → x)( → x() → (x).
Here, we have S'=()(), which is a balanced parenthesis string.

Sample Input 2

()ox

Sample Output 2

2

Sample Input 3

()oxo(xxx))))oox((oooxxoxo)oxo)ooo(xxx(oox(x)(x()x

Sample Output 3

68

见题面 Input 部分

见题面 Output 部分