P9356 "SiR-1" Bracket

> Everything that kills me makes me feel alive.

Mirika has a bracket sequence $s$ of length $n$. For a bracket sequence $S$, Mirika can perform two operations: - Rotation: choose a position $i$ satisfying $1 \leq i \leq \lvert S \rvert$, and change $S$ into $S_iS_{i+1}\cdots S_{\lvert S\rvert}S_1S_2\cdots S_{i-2}S_{i-1}$. - Insertion: insert one bracket (either a left bracket or a right bracket) at **any position** in the sequence. Mirika defines the weight $f(S)$ of a bracket sequence $S$ as the minimum number of operations needed to turn this bracket sequence into a valid bracket sequence. The definition of a valid bracket sequence is: + The empty string is a valid bracket sequence. + If $\texttt A$ is a valid bracket sequence, then $\texttt{(A)}$ is also a valid bracket sequence. + If both $\texttt A$ and $\texttt B$ are valid bracket sequences, then $\texttt{AB}$ is also a valid bracket sequence. Now Mirika wants to compute: $\sum_{l=1}^n \sum_{r=l}^n f(s[l,r])$ where $s[l,r]$ denotes the contiguous subsequence formed by $s_l,s_{l+1},\cdots,s_r$. However, Mirika is too weak to compute it, so she has to ask you for help.

**There are multiple test cases in each test point.** The first line contains a positive integer $T$, denoting the number of test cases. For each test case, the first line contains a positive integer $n$. The second line contains a bracket sequence $s$ of length $n$.

Output a total of $T$ lines. The $i$-th line contains one integer, denoting the answer for the $i$-th test case.

### Sample Explanation For $s = \texttt{())(}$: + Consider $s[1,4]=\texttt{())(}$. Perform a rotation operation with $i=4$, then $\texttt{())(} \Rightarrow \texttt{(())}$. Since $\texttt{(())}$ is a valid bracket sequence, $f(s[1, 4]) = 1$. It can be proven that there is no better strategy. + Consider $s[2,4]=\texttt{))(}$. Perform a rotation operation with $i=2$, then insert a left bracket at the beginning of the sequence, then $\texttt{))(} \Rightarrow \texttt{)()} \Rightarrow \texttt{()()}$. Since $\texttt{()()}$ is a valid bracket sequence, $f(s[2, 4]) = 2$. It can be proven that there is no better strategy. ### Constraints and Notes **This problem uses bundled test.** + Subtask 0 (15 pts): $n \leq 400$, $\sum n \leq 800$. + Subtask 1 (20 pts): $n \leq 2\times 10^3$, $\sum n \leq 4\times 10^3$. + Subtask 2 (5 pts): $s$ contains no right brackets. + Subtask 3 (10 pts): for all integers $1\le i < n$, $s_i \neq s_{i+1}$. + Subtask 4 (30 pts): $n \leq 2\times 10^5$, $\sum n \leq 5\times 10^5$. + Subtask 5 (20 pts): no special constraints. For all testdata, $1 \leq T \leq 10000$, $1 \leq n \leq 2 \times 10^6$, $1 \leq \sum n \leq 2 \times 10^7$. Translated by ChatGPT 5