题目描述

给定一个长度为偶数、仅由 ( 和 ) 组成的字符串。每次操作可以把其中一个左括号改成右括号，或把一个右括号改成左括号。

请计算至少需要修改多少个括号，才能使整个字符串成为合法括号序列。

合法括号序列满足：从左到右的任意前缀中，左括号数量都不少于右括号数量，并且整个序列中两种括号的数量相等。

输入格式

第一行包含一个长度为偶数的括号字符串。

输出格式

输出一个整数，表示最少修改次数。

())(((

3

((())))()(

2

数据范围与提示

• $2 \le |S| \le 100000$
• $|S|$ 为偶数
• $S$ 仅由 ( 和 ) 组成