如果可以通过在序列中插入字符“+”和“1”来获得正确的算术表达式,则该序列称为正则括号序列。例如,序列《(())()》、《()》和《(()(()))》是规则的,而《)(》、《(()》和《(()))(》则不是。
有一天,约翰尼得到了括号序列。他决定从中删除一些括号,以获得规则的括号序列。能得到的正则括号序列的最大长度是多少?
输入
输入由一行包含非空字符串 «(» 和 «)» 字符组成。它的长度不超过106。
输出
输出常规括号序列的最大可能长度。
示例
输入 #1
(()))(
输出 #1
4
输入 #2
((()())
输出 #2
6