题目描述

给出一个仅由 ( 和 ) 构成的括号字符串。

定义合法的括号串为：左右小括号正确匹配的括号串，需满足所有左右小括号正确嵌套，且每个左括号能唯一匹配对应的右括号、每个右括号有唯一的左括号与其匹配。 例如：(())()、()((())) 均为合法括号串；)(、(()、)(()、()( 均为非法括号串。

请编程求出给定括号串中合法括号子串的数量。 括号子串定义：从原括号串中取出的任意连续字符组成的子串；需注意，在原串不同位置取出内容相同的合法括号子串，视为不同的合法括号子串。

输入格式

一行一个字符串，仅由左小括号 ( 和右小括号 ) 构成，表示给定的括号串。

输出格式

一行一个整数，表示给定括号串中合法括号子串的总数量。

样例输入1

(())()

样例输出1

4

样例输入2

((())(

样例输出2

2

样例输入3

(()())()

样例输出3

6

样例解释（样例1）

样例1的输入为 (())()，其中合法的括号子串共4个，对应原串中如下加粗的连续部分：

1. (())()
2. (())()
3. (())()
4. (())()

数据范围

• 对于50%的数据，括号串的长度 $L$ 满足 $1 \le L \le 50$；
• 对于100%的数据，括号串的长度 $L$ 满足 $1 \le L \le 1000000$。