题目描述

奶牛贝西正试图在她的新笔记本电脑上输入一系列平衡的括号，但她太笨拙了，以至于她一直错误地输入字符。请帮助她计算字符串中必须翻转的最小字符数（例如，将左括号改为右括号，反之亦然），以便字符串保持平衡（括号合法）。

例如：() (()) ()(()()) 是平衡的，而 )( ())( ((()))) 是不平衡的。

输入格式

一行字符串，仅包括前后括号。

输出格式

使其平衡的最小修改字符数。

输入输出样例

())(

2

数据范围

对于所有数据，$2 \le \text{字符串长度} \le 10^5$，并且长度为偶数。