题目描述

奶牛 Bessie 正试图在她的新笔记本电脑上输入一个平衡的括号字符串，但由于她的蹄子很大（因此非常笨拙），她不断地输入错误的字符。 请通过计算要使该字符串变为平衡，最少需要反转多少个字符（例如，将左括号变为右括号，或反之）来帮助她。

对于“括号字符串平衡”有几种定义方法。 或许最简单的定义是，字符串中的 ( 和 ) 总数必须相同，并且对于字符串的任何前缀，( 的数量必须不少于 ) 的数量。 例如，以下字符串都是平衡的：

()

(())

()(()())

而以下则不平衡：

)(

())(

((())))

输入格式

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

输出格式

一个整数，表示要将该字符串变为平衡字符串，最少需要反转的括号数量。

())( 

2 

提示

样例解释

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