在跳蚤国，国王梦想着制造出第一辆伏特多轮（Polycycle）。设计这辆汽车需要构建一个稳固的支撑结构，这个结构像由许多括号串连成的复杂模式，以保证汽车的安全性和稳定性。
在这个挑战中，你需要理解何为合法的括号序列：
- 单一的一对括号
()表示一个基础的括号序列。 - 如果 $A$ 是一个合法的括号序列，则
($A$)也是一个合法的括号序列。 - 如果 $A,B$ 都是合法的括号序列，则 $AB$ 也是一个合法的括号序列。
现在，你将得到一串由左括号 (、右括号 ) 以及问号 ? 构成的字符串 $S$，代表伏特多轮的支撑结构的图纸设计草图。我们称 $S$ 的一个区间 $[l, r]$ 是有希望合法的，当且仅当存在一种将该区间内的问号替换为左括号或右括号的方式，使得区间内的字符能按顺序组成一个合法的括号序列。
你的任务是求出 $S$ 有多少个区间 $[l, r]$ 是有希望合法的。
输入格式
输入只有一行，包含一个字符串 $S$。
输出格式
输出一行一个整数，表示答案。
样例一
input
(())
output
2
explanation
这组样例合法区间为$[1,4]$和$[2,3]$。
样例二
input
??????????
output
25
explanation
这组样例$[l, r]$ 是有希望合法的当且仅当其为长度为偶数的非空区间。
长度为$i$的区间有$n-i+1$个，$n$为字符串$S$长度。故答案为$\sum_{i=1}^{n/2}{n-2i+1}=25$。
样例三
input
(??)??
output
8
explanation
这组样例的有希望合法的区间有$[1,2]$,$[1,4]$,$[1,6]$,$[2,3]$,$[2,5]$,$[3,4]$,$[3,6]$,$[5,6]$,共$8$个区间。
数据范围
对于全部数据：记 $n=|S|$，$1\leq n \leq 10^6$。
| 子任务编号 | $n\leq$ | 特殊性质 | 分值 |
|---|---|---|---|
| $1$ | $10^6$ | $S$ 中只含 ? |
$5$ |
| $2$ | $S$ 中不含 ? |
$10$ | |
| $3$ | $20$ | 无 | $15$ |
| $4$ | $5000$ | $15$ | |
| $5$ | $2\times 10^5$ | $15$ | |
| $6$ | $10^6$ | $S$ 中不含 ) |
$20$ |
| $7$ | 无 | $20$ |
时间限制：$1\texttt{s}$
空间限制：$512\texttt{MB}$
鄂公网安备 42010202000505 号