题目描述

给定一个由 (、)、o、x 组成的字符串 $S$。你可以任意次数地交换 $S$ 中相邻的两个字符。请你求出，为了满足下述条件，所需的最小操作次数。

• 将 $S$ 中出现的每个 o 替换为 ()，每个 x 替换为 )(，从而得到仅由 ( 和 ) 组成的新字符串 $S'$。此时，$S'$ 必须是括号匹配的字符串。

括号匹配的字符串定义如下：

• 空字符串；
• 存在括号匹配的非空字符串 $s$、$t$，将 $s$ 和 $t$ 按此顺序连接得到的字符串；
• 存在括号匹配的字符串 $s$，将 (、$s$、) 按此顺序连接得到的字符串。

此外，根据本题的限制条件，目标一定可以实现。

输入格式

输入为一行，包含一个字符串 $S$。

输出格式

输出所需的最小操作次数。

输入输出样例 #1

输入 #1

)x(

输出 #1

3

输入输出样例 #2

输入 #2

()ox

输出 #2

2

输入输出样例 #3

输入 #3

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

输出 #3

68

说明/提示

限制

• $S$ 仅由 (、)、o、x 组成。
• $S$ 至少包含一个 ( 和一个 )，且它们的数量相等。
• $|S| \leq 8000$

样例解释 1

)x( → x)( → x() → (x)，这样操作即可。此时 $S' = ()()`，它是一个括号匹配的字符串。