$Bessie$刚购买了一台新的笔记本电脑，但不幸的是，鉴于大蹄子相对于小键盘的大小，她发现自己无法打字。

$Bessie$刚刚尝试输入她最喜欢的模式之一，括号中的平衡字符串。 但是，她意识到自己可能打错了一个字符，不小心替换了用“（”替换了“）”，或者用“）”替换了“（”。

请你帮助$Bessie$计算字符串中的位置数，以便反转该位置处的单个括号会导致整个字符串变得平衡。

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

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

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

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

而其他则不是：

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

输入格式

第1行：一串长度为$N$的括号$（1 \leq N \leq 100,000）$。数据保证字符串的开头不会是“）”。

输出格式

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

样例

样例输入

()(())))

样例输出

4

样例解释

仔细观察输入字符串：

12345678
()(())))

我们发现在位置$2$处反转括号的方向会导致一个平衡的字符串：

12345678 
(((())))

同样，在位置$5$，位置$6$或位置$7$处反转括号

数据范围与提示

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

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

阿里云盘大样例下载

夸克云盘大样例下载