そこそこバランスのとれた括弧列

시간 제한8초메모리 제한512 MB

요약

주어진 괄호 문자열에 괄호를 원하는 위치에 추가하여 'そこそこバランスのとれた括弧列'로 만들 때 필요한 최소 추가 개수를 구한다.

문제

「そこそこバランスのとれた括弧列」とは，以下のいずれかの条件を満たす文字列である．

空文字列
そこそこバランスのとれた括弧列 A が存在し，'(' を 1 個または 2 個, A, ')' を 1 個または 2 個 をこの順に結合した文字列
空文字列でないそこそこバランスのとれた括弧列 A, B が存在し，A, B をこの順に結合した文字列

たとえば，'())' や '())(()()' などはそこそこバランスのとれた括弧列であるが，'((' や '()))((()' などはそこそこバランスのとれた括弧列ではない．

'(' と ')' のみからなる文字列 S が与えられる．S がそこそこバランスのとれた括弧列になるように括弧を追加する．ただし，括弧はどの位置に追加しても良い．追加する最小の括弧の数を求めよ．

入力は最大 50 データセットからなる．各データセットは 1 行からなり，長さが 1 以上 2 × 105 以下の '(' と ')' のみからなる文字列が与えられる．

入力の終わりは，'#' からなる行で表される．文字列の長さの合計は 5 × 106 を超えない．

各データセットについて，そこそこバランスのとれた括弧列にするために追加する最小の括弧の数を 1 行に出力せよ．

예제 1

입력

(()
())()(()
((()))))
))(()(
))()()))()(((())))))))((((()(
#

예상 출력