Problem4933--幸运分

4933: 幸运分

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

OJ 管理员最近对仅有 '('')' 组成的字符串很感兴趣。对于一个这样的字符串,管理员会从左到右依次看每一个括号,如果它遇到了一个左括号,就不做任何操作,如果它遇到了一个右括号,它就会往前找到第一个还没用过的左括号跟这个右括号匹配,并标记这个左括号为用过。如果没有找到能匹配的左括号就忽略这个右括号继续看后边的括号。
管理员认为一个这样的字符串的幸运分数为按上述匹配方法能匹配的括号对数,你能帮他算算他手上这个仅有 '('')' 组成的字符串的幸运分数吗?

Input

输入一行,包含一个整数仅由 '('')' 组成的字符串,字符串长度不超过 $10 ^ 5$。

Output

输出一行,包含一个整数,表示这个字符串的幸运分数。

Constraints

对于 $60\%$ 的数据,$1 \leq$ 字符串长度 $\leq 10 ^ 3$
对于 $100\%$ 的数据,$1 \leq$ ≤字符串长度 $\leq 10 ^ 5$

Sample 1 Input

((()

Sample 1 Output

1

Source/Category