题目描述

小花正在电脑上输入一个合法的括号序列，但由于她打字速度太快，经常按错键。

请你帮她计算：最少需要反转多少个括号字符（将 ( 变为 )，或将 ) 变为 (），才能使得输入的字符串变成一个合法的括号序列。

一个合法的括号序列需要满足：

• 字符串中 ( 和 ) 的总数相等。
• 对于字符串的任意前缀，( 的数量不少于 ) 的数量。

输入格式

一行，一个只包含 ( 和 ) 的字符串，长度为偶数，最多 $100000$ 个字符。

输出格式

一行，一个整数，表示最少需要反转的括号数量。

样例

())(

2

提示

样例解释

最后一个括号必须被反转，两个中间的右括号中也必须有一个被反转。

数据范围：字符串长度为偶数且不超过 $10^5$。