括号匹配

Problem Description

本题中字符串下标从 $1$ 开始。 对于字符串 $S$，我们称 $S$ 的非空子串为其中连续一段字符构成的字符串。第 $l$ 个字符到第 $r$ 个字符（$l\le r$）构成的子串记作 $S \left[l\ldots r \right]$。 称非空字符串 $S$ 是回文串，当且仅当把所有字符的顺序翻转过来后 $S$ 保持不变。例如 ()() 不是回文串，而 ())( 是回文串。 称非空字符串 $S$ 是括号串，当且仅当 $S$ 中只有 ( 和 ) 且两种字符一样多，并且对于任意的 $i$，$S \left[ 1\ldots i \right]$ 中 ( 的数量 不少于 )。例如 () 是括号串，而 ())(() 不是括号串。 给出一个字符串 $S$，求 $S$ 有多少个子串 $T$ 同时满足：

• $T$ 是回文串。
• $T$ 中存在一个子串是括号串。 两个子串的下标范围不同，我们就认为两个子串不同。

Input

输入一行一个字符串 $S$（$1\le |S|\le 10^4$，$S$ 中仅含小写字母和小括号），含义同题目描述。

Output

输出一行一个自然数，表示答案。

Sample Input

()(a)a()(

Sample Output

4

Hint

()( 是回文子串，其中 () 是括号串。由于这个子串出现了两次，所以算两个子串。另外两个串分别是 )(a)a() 和 ()(a)a()(。 注意 (a)a( 也是回文子串，但是其中不包含子串是括号串，所以不计入答案。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（9）