题目描述

给定一个长度为偶数的、只由 ( 和 ) 组成的字符串 $S$。

一次操作可以任选一个字符，把 ( 改成 )，或者把 ) 改成 (。

求最少操作多少次，能使 $S$ 变成合法括号序列。

合法括号序列的定义：

• 空串是合法括号序列；
• 若 $A$ 是合法括号序列，则 (A) 也是合法括号序列；
• 若 $A,B$ 都是合法括号序列，则 $AB$ 也是合法括号序列。

输入格式

一行一个字符串 $S$。

输出格式

一行一个整数，表示最少操作次数。

样例

)(

2

())(

2

((

1

()()

0

样例解释

• )(：两个字符都要改，改成 ()，共 $2$ 次。
• ())(：把第 $3$ 个字符 ) 改成 (、第 $4$ 个字符 ( 改成 )，得到 ()()，共 $2$ 次；只改一个字符无法合法。
• ((：改第二个字符为 )，得到 ()，共 $1$ 次。
• ()()：已经合法，$0$ 次。

数据范围

对于所有测试数据，保证 $2\le |S|\le 10^6$，$|S|$ 为偶数，字符串只包含 ( 和 )。