# E.智乃的合法的“回文”括号数目

## 题目描述

<blockquote>

$\hspace{15pt}$睡了么？  
$\hspace{15pt}$$\texttt{"(())"}$ 不是回文，$\texttt{"())("}$ 才是回文.jpg。

</blockquote>

$\hspace{15pt}$现在有一个仅由字符 $\texttt{`('}$ 和 $\texttt{`)'}$ 组成的，长度为 $n$ 的字符串 $s = s_1s_2\dots s_n$，智乃想知道它有多少个非空的连续子串 $s'$，满足：
$\hspace{23pt}\bullet\,$$s'$ 是一个<u>合法括号串</u>；
$\hspace{23pt}\bullet\,$对于子串的第 $i \left(1 \leqq i \leqq |s'|\right)$ 个字符，满足 $s'_i \neq s'_{|s'|-i+1}$。
$\hspace{15pt}$您只需要直接输出满足条件的子串数目。

【名词解释】
$\hspace{15pt}$$|s'|$ 表示字符串 $s'$ 的长度。
$\hspace{15pt}$如果在括号串中插入字符 $\texttt{+}$ 和 $\tt 1$ 就可以得到正确的算术表达式，那么这个括号串就称为<u>合法的括号串</u>。例如，$\texttt{""}$、$\texttt{"(())"}$ 和 $\texttt{"()()"}$ 是合法的括号串，因为填入内容后可以表示为 $\texttt{"1"}$、$\texttt{"((1))"}$ 和 $\texttt{"(1)+(1)"}$。更严格地，一个括号串被称为合法的括号串，当且仅当：
${\hspace{20pt}}_\texttt{1.}\,$空串是合法的括号串；
${\hspace{20pt}}_\texttt{2.}\,$如果 $A$ 是合法的括号串，那么 $\texttt{"(}A\texttt{)"}$ 也是合法的括号串；
${\hspace{20pt}}_\texttt{3.}\,$如果 $A$ 和 $B$ 都是合法的括号串，那么 $AB$ 也是合法的括号串。

## 输入描述

$\hspace{15pt}$第一行输入一个整数 $n \left(1\leq n \leq 10^5\right)$，表示输入的字符串长度。 
$\hspace{15pt}$第二行输入一个长度大小为 $n$，仅由 $\texttt{`('}$ 和 $\texttt{`)'}$ 两种字符组成的字符串 $s$，表示初始字符串。

## 输出描述

$\hspace{15pt}$输出一个整数，表示合法的“回文”括号数目。

## 样例

~~~text input:#1
6
()()()
~~~
~~~text output:#1
6
~~~

$\hspace{15pt}$在这个样例中，区间 $[1,2]$、$[3,4]$、$[5,6]$、$[1,4]$、$[3,6]$、$[1,6]$ 均满足题意。

~~~text input:#2
6
((()))
~~~
~~~text output:#2
3
~~~

$\hspace{15pt}$在这个样例中，区间 $[3,4]$、$[2,5]$、$[1,6]$ 均满足题意。

~~~text input:#3
5
)))))
~~~
~~~text output:#3
0
~~~

~~~text input:#4
2
)(
~~~
~~~text output:#4
0
~~~

~~~text input:#5
30
(()(()()())()(())()(()()())())
~~~
~~~text output:#5
26
~~~