该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

两难

想走还是想留

向左还是向右

——加木《两难》

题目背景

她把这串括号写在草稿纸的最下面。

( 是向左，) 是向右。每写下一个，就像替一段关系做一次选择：想走，还是想留；向左，还是向右。

朋友说，一段关系要成立，有两个条件：任何时刻，你给出去的都不能少于收回来的；而到最后，向左和向右必须一样多。

她低头数了数纸上的符号，发现有些地方，写反了。

于是她拿起笔，一个一个地改。每改一个，就像把当初那个犹豫不决的自己，重新推回岔路口。

想走还是想留。

向左还是向右。

改到最后一个时，她忽然停住了。原来有些关系，无论改掉几个符号，都只是让它看起来更接近完整；而真正缺掉的那一半，从来不在纸上。

题目描述

给定一个长度为偶数的括号串，串中只包含 ( 和 )。

一次操作可以把任意一个字符翻转：( 变成 )，或者 ) 变成 (。

请问至少需要多少次操作，才能把字符串变成合法的括号序列？

合法括号序列是指：任意前缀中 ( 的数量不少于 ) 的数量，且整个串中两种括号数量相等。

输入格式

一行一个字符串 $s$。

输出格式

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

样例

))((

2

样例 #2：

())(()

2

样例 #3：

()

0

数据范围

$2 \le |s| \le 10^5$，且 $|s|$ 为偶数。

提示：括号总能改对，有些关系不能。