配点 : $1000$ 点

問題文

(, ), o, x からなる文字列 $S$ が与えられます． あなたは，$S$ の隣接する $2$ 文字をswapする操作を好きな回数行うことができます． 次の条件を達成するために必要な最小の操作回数を求めてください．

• $S$ に登場するすべての o を () で，x を )( で置き換え，( と ) のみからなる文字列 $S'$ を作る． この時，$S'$ は括弧の対応が取れている文字列である．

制約

• $S$ は (, ), o, x からなる文字列
• $S$ は $1$ つ以上の ( と ) を含み，またそれらの個数は等しい
• $|S| \leq 8000$

入力

入力は以下の形式で標準入力から与えられる．

$S$

出力

答えを出力せよ．

)x(

3

)x( → x)( → x() → (x) と操作すればよいです． このとき，$S'=$()() であり，これは括弧の対応の取れている文字列です．

()ox

2

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

68