A - Depth of Parentheses Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君は、数学の式に含まれる括弧の構造を解析するプログラムを作成しています。

数学の式では、括弧を使って計算の優先順位を表現します。括弧は入れ子にすることができ、括弧の中にさらに括弧を含めることで、複雑な計算順序を指定できます。高橋君は、まず括弧だけを取り出して、その入れ子の深さを調べることにしました。

( と ) のみからなる文字列 S が与えられます。S の長さを N とし、文字列の各文字を先頭から順に 1, 2, \ldots, N 番目と番号づけます。i 番目の文字における深さを、i 番目の文字より前にあるすべての文字（すなわち 1 番目から i-1 番目までの文字）に含まれる ( の個数から ) の個数を引いた値と定義します。i = 1 のときは、それより前に文字が存在しないため、深さは 0 です。

例えば、((())) の各文字の深さは、左から順に 0, 1, 2, 3, 2, 1 です。4 番目の文字 ) では、それより前の 3 文字がすべて ( であるため、深さは 3 - 0 = 3 となります。この文字列における深さの最大値は 3 です。また、(()()) の各文字の深さは、左から順に 0, 1, 2, 1, 2, 1 であり、深さの最大値は 2 です。

文字列 S が与えられるので、S の各文字の深さのうち最大値を求めてください。

制約

  • 2 \leq N \leq 10^6（N は文字列 S の長さ）
  • S は ( と ) のみからなる
  • S は正しく対応のとれた括弧列である。すなわち、以下の条件をともに満たす：
  • 先頭から任意の位置までにおいて、( の個数は ) の個数以上である
  • 文字列全体では ( と ) の個数が等しい

入力

S
  • 1 行目に、括弧の文字列 S が与えられる。入力はこの 1 行のみである。

出力

S の各文字の深さのうち最大値を 1 行で出力してください。

入力例 1

((()))

出力例 1

3

入力例 2

(()(())(()))

出力例 2

3

入力例 3

((((()))))((()))(())()(((((())))))

出力例 3

6

Score : 233 pts

Problem Statement

Takahashi is creating a program to analyze the structure of parentheses contained in mathematical expressions.

In mathematical expressions, parentheses are used to express the priority of calculations. Parentheses can be nested, and by including further parentheses within parentheses, complex calculation orders can be specified. Takahashi decided to first extract only the parentheses and examine the depth of their nesting.

You are given a string S consisting only of ( and ). Let N be the length of S, and number each character of the string from the beginning as the 1st, 2nd, \ldots, Nth character. The depth at the i-th character is defined as the number of ( minus the number of ) among all characters before the i-th character (that is, from the 1st to the (i-1)-th character). When i = 1, there are no characters before it, so the depth is 0.

For example, the depth of each character in ((())) is, from left to right, 0, 1, 2, 3, 2, 1. For the 4th character ), all 3 characters before it are (, so the depth is 3 - 0 = 3. The maximum depth in this string is 3. Also, the depth of each character in (()()) is, from left to right, 0, 1, 2, 1, 2, 1, and the maximum depth is 2.

Given the string S, find the maximum value among the depths of all characters in S.

Constraints

  • 2 \leq N \leq 10^6 (N is the length of string S)
  • S consists only of ( and )
  • S is a correctly matched parenthesis sequence. That is, it satisfies both of the following conditions:
  • At any position from the beginning, the number of ( is at least the number of )
  • In the entire string, the number of ( and ) are equal

Input

S
  • The first line contains the parenthesis string S. The input consists of only this single line.

Output

Print the maximum value among the depths of all characters in S in one line.

Sample Input 1

((()))

Sample Output 1

3

Sample Input 2

(()(())(()))

Sample Output 2

3

Sample Input 3

((((()))))((()))(())()(((((())))))

Sample Output 3

6