问题描述

给定一个由 ( 和 ) 组成的字符串 $S$。有多少个整数 $(i,j)$ 满足以下条件：

条件：当从字符串 $S$ 的第 $i$ 个字符到第 $j$ 个字符（包括两端字符）提取出来时，该子字符串是括号匹配的。

括号匹配的字符串是满足以下任一条件的字符串：

• 空字符串
• 存在一对括号匹配的字符串 $A, B$，将它们按顺序连接起来形成一个新的字符串
• 存在一个括号匹配的字符串 $A$，在其前面加上 (，在其后面加上 ) 形成一个新的字符串

约束条件

• $1 \leq |S| \leq 10^5$
• $S$ 是仅由 ( 和 ) 组成的字符串

输入

输入以以下格式从标准输入中给出。

$S$

输出

输出满足条件的整数对 $(i,j)$ 的数量。

示例 1

((())

输出示例 1

2

• 提取字符串 $S$ 的第 $2$ 个字符到第 $5$ 个字符，得到 (())，这是一个括号匹配的字符串。
• 提取字符串 $S$ 的第 $3$ 个字符到第 $4$ 个字符，得到 ()，这是一个括号匹配的字符串。

因此，$(2, 5)$ 和 $(3, 4)$ 满足条件。

示例 2

(()()(())(

输出示例 2

7