当威尔陷入颠倒状态时,他仍然可以通过圣诞彩灯与他的妈妈乔伊斯交流(他可以用意念打开和关闭它们)。他不能直接告诉妈妈他在哪里,因为把他带到颠倒世界的怪物会知道并重新安置他。
于是,他想出了一个谜题来告诉妈妈他的坐标。他的坐标就是下面问题的答案。
仅由括号('(' 和 ')')组成的字符串称为括号序列。某些括号序列称为正确的括号序列。更正式地说:
- 空字符串是正确的括号序列。
- 如果 s 是正确的括号序列,则 (s) 也是正确的括号序列。
- 如果 s 和 t 是正确的括号序列,则 st(s 和 t 的串联)也是正确的括号序列。
由括号和问号 ('?') 组成的字符串被称为漂亮当且仅当有一种方法可以用 '(' 或 ')' 替换每个问号,使得生成的字符串是非空的正确括号序列。
Will 给了他妈妈一个由括号和问号组成的字符串 s(通过灯光使用莫尔斯电码),他的坐标是整数对 (l, r) 的数量,使得 1 ≤ l ≤ r ≤ |s|字符串 slsl + 1... sr 很漂亮,其中 si 是 s 的第 i 个字符。
Joyce 对括号序列一无所知,所以她请求你的帮助。
输入
输入的第一行也是唯一一行包含字符串 s,仅由字符 '(', ')' 和 '?' 组成(2 ≤ |s| ≤ 5000)。
输出
在输出的第一行也是唯一一行中打印 Will 谜题的答案。
示例
输入 #1
((?))
输出 #1
4
输入 #2
??()??
输出 #2
7
注意
对于第一个示例测试用例, s 的漂亮子字符串是:
1.“(?”可以转换为“()”。
2.“?)”可以转换为“()”。
3.“((?)”可以转化为“(())”。
4.“(?))”可以转换为“(())”。
对于第二个示例测试用例, s 的漂亮子字符串是:
1.“??”可以转化为“()”。
2. "()".
3.“??()”可以转换为“()()”。
4.“?()?”可以转化为“(())”。
5.“??”可以转化为“()”。
6.“()??”可以转化为“()()”。
7.“??()??”可以转化为“()()()”。