問題文

天下一魔力発電所は不思議な魔術で電気を生み出すことができる発電所です。

魔力発電に用いる燃料は以下の様な文字列 S です。

S は ( と ) で構成されており、S の文字数は偶数です。

天下一ワープロでこの文字列を対応の取れた文字列に書き換えることで魔力発電に成功します。

対応が取れた文字列とは、以下の文字列です。

• () は対応が取れた文字列である。
• T が対応が取れた文字列であるとき、(T) も対応が取れた文字列である。
• T, U が対応が取れた文字列であるとき、TUも対応が取れた文字列である。

天下一ワープロには以下 4 通りの操作があります。

はじめはカーソルは S の先頭の文字を指します。

1. カーソルを右に動かす（カーソルが末尾の文字を指す場合は動かない）
2. カーソルを左に動かす（カーソルが先頭の文字を指す場合は動かない）
3. カーソルが指す文字が ( のとき、その文字を ) に変更する
4. カーソルが指す文字が ) のとき、その文字を ( に変更する

たとえば S が次の文字列の場合、

())(()))

1, 4 と操作を行うことで

(()(()))

という対応が取れた文字列にすることができます。

発電所の責任者であるフデくんは最も少ない操作回数で文字列を対応が取れた文字列に書き換えたいです。

S が与えられるので、対応の取れた文字列に書き換える最も少ない操作回数を求めてください。

制約

• S の文字数 |S| は偶数
• 2 \leq |S| \leq 100

入力例 1

())(()))

出力例 1

2

入力例 2

((((

出力例 2

5

入力例 3

)))(((

出力例 3

9