← 返回题目列表

Codeforces · 26/B

B. 常规括号序列

中文机器翻译题面 查看原题

如果可以通过在序列中插入字符“+”和“1”来获得正确的算术表达式,则该序列称为正则括号序列。例如,序列《(())()》、《()》和《(()(()))》是规则的,而《)(》、《(()》和《(()))(》则不是。

有一天,约翰尼得到了括号序列。他决定从中删除一些括号,以获得规则的括号序列。能得到的正则括号序列的最大长度是多少?

输入

输入由一行包含非空字符串 «(» 和 «)» 字符组成。它的长度不超过106。

输出

输出常规括号序列的最大可能长度。

示例

输入 #1

(()))(

输出 #1

4

输入 #2

((()())

输出 #2

6