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

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

1. () 是长度最小的合法的括号序列。

2. 如果 A 是合法的括号序列，则 (A) 也是合法的括号序列。

3. 如果 A 是合法的括号序列，B 是合法的括号序列，则 AB、(AB) 也是合法的括号序列。

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

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

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

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

样例 1 解释

将第 3 个括号 ) 改成 (，第 4 个括号 ( 改成 )，第 6 个括号 ( 改成 )，得到合法的括号序列 ()()()。

数据范围

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

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

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

月赛模拟2024