题目描述

给定一个字符串 $S$，它由 (，)，o和x 组成。你可以任意次数地交换 $S$ 中相邻的字符。找到满足以下条件所需的最小交换次数。

• 通过将 $S$ 中的每个 o 替换为 ()，每个 x 替换为 )(，得到一个字符串 $S'$，那么 $S'$ 是一个平衡括号串。

平衡括号串的定义

平衡括号串是以下之一：

• 空串；
• $s$ 和 $t$ 按顺序连接而成的字符串，其中 $s$ 和 $t$ 分别是非空的平衡括号串；
• 按顺序连接的 (，$s$，) 形成的字符串，其中 $s$ 是一个平衡括号串。

在此问题的约束条件下，总是可以实现目标。

约束条件

• $S$ 是一个由 (，)，o和x 组成的字符串。
• $S$ 包含相同数量的 ( 和 )。
• $|S| \\leq 8000$

输入

从标准输入读入数据，格式如下：

$S$

输出

打印答案。

示例输入 1

)x(

示例输出 1

3

我们应该按照以下方法操作：)x( → x)( → x() → (x)。在这里，我们有 $S'=$()()，它是一个平衡括号串。

示例输入 2

()ox

示例输出 2

2

示例输入 3

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

示例输出 3

68