题目描述

Bessie刚买了一台新笔记本电脑，但由于她的大蹄子相对于小键盘来说太大了，打字不太方便。她尝试输入自己最喜欢的平衡括号字符串，但可能打错了一个字符——将'('误输入为')'或反之。请帮助Bessie计算字符串中有多少个位置，如果反转该位置的单个括号（将'('改为')'或反之），会使整个字符串变为平衡的。

平衡括号字符串的定义：

1. '('和')'的总数相同
2. 对于任何前缀字符串，'('的数量不少于')'的数量

输入格式

一行：一个长度为N（1 ≤ N ≤ 100,000）的括号字符串

输出格式

一行：满足条件的位置数量

输入输出样例

输入 #1

()(())))

输出 #1

4

样例解释

输入字符串：()(()))) 位置索引：12345678

满足条件的位置：

1. 位置2：反转后变为(((())))（平衡）
2. 位置5：反转后变为()((())))（平衡）
3. 位置6：反转后变为()(()())))（平衡）
4. 位置7：反转后变为()(())()))（平衡）

因此共有4个位置满足条件。