$Bessie$刚购买了一台新的笔记本电脑，但由于她笨拙（足够大的蹄子），她经常打错字。

请通过计算字符串中必须反转的最小字符数,（例如，将左括号改为右括号，反之亦然）来帮助她，以使字符串变得平衡。

有几种方法可以定义括号“平衡”的含义。

最简单的定义是必须有相同的总数“（” 和“）”，所有括号都是匹配的。

例如，以下字符串都是平衡的：

（）
（（））
（）（（）（））

而其他则不是：

）（
（））（
（（（））））

输入格式

第1行：一串长度为$N$的括号$（1 \leq N \leq 100,000）$。

输出格式

第1行：输入字符串中，能使在单个位置上反转括号导致整个字符串变得平衡的位置个数。

样例

样例输入

())(

样例输出

2

样例解释

必须切换最后一个括号，因此也必须切换中间两个右括号之一。

数据范围与提示

• 对于 $100 \\%$ 的数据，$1 \leq N \leq 100,000$。
• 时间限制：$1\mathrm{s}$
• 空间限制：$256\mathrm{MB}$

大样例下载

百度网盘大样例下载 提取码: GFOI

阿里云盘大样例下载

夸克云盘大样例下载