题目描述

给定长度为 n 的一个括号序列，每次修改可以修改一个位置的括号，若这个括号为 (，则修改为 )，若这个括号为 )，则修改为 (，问最少修改多少个使得原括号序列合法。

其中：

1. () 是合法的；

2. 若 A 是合法的，则 (A) 是合法的；

若 A、B 都是合法的，则 AB 是合法的。

输入格式

一个长度为 n 个括号序列。

输出格式

最少的修改次数。

输入样例 #1

())(

输出样例 #1

2

输入样例 #2

()

输出样例 #2

0

输入样例 #3

)(

输出样例 #3

2

数据范围与约定

100% 的数据满足：1≤n≤100,000。