「そこそこバランスのとれた括弧列」とは,以下のいずれかの条件を満たす文字列である.
- 空文字列
- そこそこバランスのとれた括弧列 A が存在し,'(' を 1 個または 2 個, A, ')' を 1 個または 2 個 をこの順に結合した文字列
- 空文字列でないそこそこバランスのとれた括弧列 A, B が存在し,A, B をこの順に結合した文字列
たとえば,'())' や '())(()()' などはそこそこバランスのとれた括弧列であるが,'((' や '()))((()' などはそこそこバランスのとれた括弧列ではない.
'(' と ')' のみからなる文字列 S が与えられる.S がそこそこバランスのとれた括弧列になるように括弧を追加する.ただし,括弧はどの位置に追加しても良い.追加する最小の括弧の数を求めよ.
入力は最大 50 データセットからなる.各データセットは 1 行からなり,長さが 1 以上 2 × 105 以下の '(' と ')' のみからなる文字列が与えられる.
入力の終わりは,'#' からなる行で表される.文字列の長さの合計は 5 × 106 を超えない.