当前没有测试数据。

题目描述

给出一个仅由 ( 和 ) 构成的括号字符序列。

如果括号序列能满足如下的定义，则称之为合法的括号序列。

• () 是长度最小的合法的括号序列。
• 如果 A 是合法的括号序列，则 (A) 也是合法的括号序列。
• 如果 A 是合法的括号序列，B 是合法的括号序列，则 AB、(AB) 也是合法的括号序列。

比如：(())()、()((())) 都是合法的括号序列。而 )(、(()、)(()、`()( 都不是合法的括号序列。

给出一个长度为偶数的括号序列，请编程计算出，该括号序列最少要修改多少个括号，可以使其成为合法的括号序列。

输入格式

输入一个仅由 ( 和 ) 构成的长度为偶数的括号字符序列。

输出格式

输出一个整数，表示最少要修改多少个括号，可以使其成为合法的括号序列。

样例

输入

())(((

输出

3

输入

((())))()(

输出

2

数据范围

对于 $20\%$ 的数据，满足输入序列的长度 $\le 10$。

对于 $50\%$ 的数据，满足输入序列的长度 $\le 2000$。

对于 $100\%$ 的数据，满足输入序列的长度 $\le 100,000$ 且为偶数。