305 . 括號國

Description

括號國是一個奇怪的國家，那裡的人民非常喜歡左小括號 $\mathtt{\text{(}}$$\texttt{(}$ 以及右小括號 $\mathtt{\text{)}}$$\texttt{)}$，因此兩個括號國的人民很常使用括號語作為溝通的方式。舉例來說：

「$\mathtt{\text{))(()()}}$$\texttt{))(()()}$」

「$\mathtt{\text{)()(()()()}}$$\texttt{)()(()()()}$」

上述呈現了兩個人的對話，其中一個人在膜拜，另一個人在裝弱。

在那裡的競程選手也喜歡使用括號語來表示一道題目，像是：

「$\mathtt{\text{)()))(()())))(()())))()()()))()()))()((()))()))))((())}}$$\texttt{)()))(()())))(()())))()()()))()()))()((()))()))))((())}$」

經由翻譯後，這道題目的意思是：

「給定一個由 $\mathtt{\text{()}}$$\texttt{()}$ 組成的字串，請問它所有子字串的最長合法括號子序列長度總和為何？」

你不想輸給括號國的競程選手，因此請想辦法解決這個問題。

一個括號字串為合法括號若它滿足以下條件：

• 該字串的 $\mathtt{\text{(}}$$\texttt{(}$ 與 $\mathtt{\text{)}}$$\texttt{)}$ 出現次數相同

• 對於該字串的任意前綴，其 $\mathtt{\text{(}}$$\texttt{(}$ 的數量皆不小於 $\mathtt{\text{)}}$$\texttt{)}$

一個括號字串 $s_1{s}_2,\dots ,s_N$$s_1s_2, \ldots, s_N$ 的最長合法括號子序列為最長的序列 $a_1<a_2<\dots <a_K$$a_1 < a_2 < \ldots < a_K$ 使 $s_{a_1}{s}_{a_2},\dots ,s_{a_K}$$s_{a_1}s_{a_2}, \ldots, s_{a_K}$ 是一個合法括號。

一個長度為 $N$$N$ 的字串有 $(\genfrac{}{}{0ex}{}{N+1}{2})$$\binom{N + 1}{2}$ 個子字串，對於任意 $1\le l\le r\le N$$1 \leq l \leq r \leq N$，$s_l{s}_{l+1},\dots ,s_r$$s_ls_{l + 1}, \ldots, s_r$ 皆為字串 $s$$s$ 的子字串。

Input Format

輸入第一行有一個整數 $N$$N$，代表括號字串的長度。

輸入第二行有一個由 $\mathtt{\text{(}}$$\texttt{(}$ 與 $\mathtt{\text{)}}$$\texttt{)}$ 組成的字串 $S$$S$。

• $1\le N\le 2\times {10}^5$$1 \leq N \leq 2 \times 10^ 5$

• $|S|=N$$|S| = N$

• $S_i\in \{\mathtt{\text{(}},\mathtt{\text{)}}\}$$S_i \in \lbrace\texttt{(}, \texttt{)}\rbrace$

Output Format

請輸出一行，上面有一個數字代表答案。

Sample Input 1

4
()()

Sample Output 1

xxxxxxxxxx
12

Sample Input 2

xxxxxxxxxx
8
)))(((((

Sample Output 2

xxxxxxxxxx
0

Sample Input 3

xxxxxxxxxx
7
)(()))(

Sample Output 3

xxxxxxxxxx
36

Hints

令 $f(l,r)$$f(l,r)$ 為 $S_l{S}_{l+1},\dots ,S_r$$S_lS_{l + 1}, \ldots ,S_r$ 的最長合法括號子序列長度，以下為範例測資一中所有可能的函數值：

• $f(1,1)=0$$f(1,1)=0$

• $f(2,2)=0$$f(2,2)=0$

• $f(3,3)=0$$f(3,3)=0$

• $f(4,4)=0$$f(4,4)=0$

• $f(1,2)=2$$f(1,2)=2$

• $f(2,3)=0$$f(2,3)=0$

• $f(3,4)=2$$f(3,4)=2$

• $f(1,3)=2$$f(1,3)=2$

• $f(2,4)=2$$f(2,4)=2$

• $f(1,4)=4$$f(1,4)=4$

而答案為所有數值加總，也就是 $12$$12$。

Subtasks

Testdata and Limits