You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

奶牛贝茜试图在她的新笔记本电脑上输入一个平衡的括号字符串，但由于年龄太小，她总是输错字符。请帮她计算一下，要使字符串变得平衡，最少需要反转多少个字符（例如，将左括号改成右括号，或反之）。

有几种方式来定义一个括号字符串 “平衡” 的含义。也许最简单的定义是，左括号 “(” 和右括号 “)” 的总数必须相同，并且对于字符串的任何前缀，左括号的数量必须至少与右括号的数量一样多。例如，以下字符串都是平衡的：

() (()) ()(()())

而以下这些则不是：

)( ())( ((()))) 给出一个偶数长度的括号序列，问最少修改多少个括号可以使其平衡。

输入格式

• 第1行：一个长度为偶数且最多包含100,000个字符的括号字符串。

输出格式

• 第1行：一个整数，表示将该字符串转换为平衡字符串必须翻转的最少括号数量。

输入输出样例 #1

输入 #1

())(

输出 #1

2

说明/提示

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