题目描述

小x发现了一个藏宝图，而这个藏宝图肯定是加密的。在藏宝图的表面上有一个只包含左右小括号的字符串，解开这个藏宝图的密码就和这个字符串有关。

首先定义平衡的概念：

1）整体左右括号个数必须相等；

2）在字符串的任意一个前缀中，左括号的个数必须大于等于右括号的个数。

比如下面的括号序列肯定是平衡的：

()

(())

()(()())

而下面的这些就不是平衡的：

)(

())(

((())))

而解开藏宝图的秘密就是，藏宝图中的序列不一定是平衡的，问最少改变多少个括号，能让这个字符串变平衡.

输入格式

一个长度为N字符串，字符串中字符保证是左右括号。 N<=100000

输出格式

一个整数，表示最少改变多少个括号，能让这个字符串变平衡。

样例数据

input

())(

output

2

最后一个必须改变，第3个也必须变，所以需要改变2个

数据规模与约定

30% N<=50

50% N<=700

100% N<=100000

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$

bzoj 3016