← 返回题目列表

Codeforces · 917/A

A. 怪物

中文机器翻译题面 查看原题

当威尔陷入颠倒状态时,他仍然可以通过圣诞彩灯与他的妈妈乔伊斯交流(他可以用意念打开和关闭它们)。他不能直接告诉妈妈他在哪里,因为把他带到颠倒世界的怪物会知道并重新安置他。

于是,他想出了一个谜题来告诉妈妈他的坐标。他的坐标就是下面问题的答案。

仅由括号('(' 和 ')')组成的字符串称为括号序列。某些括号序列称为正确的括号序列。更正式地说:

- 空字符串是正确的括号序列。
- 如果 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.“??()??”可以转化为“()()()”。