在跳蚤国，国王梦想着制造出第一辆伏特多轮（Polycycle）。设计这辆汽车需要构建一个稳固的支撑结构，这个结构像由许多括号串连成的复杂模式，以保证汽车的安全性和稳定性。

在这个挑战中，你需要理解何为合法的括号序列：

1. 单一的一对括号 () 表示一个基础的括号序列。
2. 如果 $A$ 是一个合法的括号序列，则 ($A$) 也是一个合法的括号序列。
3. 如果 $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\le n\le {10}^6$。

时间限制：$1\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$