P15730 [JAG 2024 Summer Camp #2] Broken Parentheses

Let us define a **correct parenthesis sequence** as a string that satisfies any of the following conditions: - It is an empty string. - It is formed by concatenating $($, $A$, $)$ in this order where $A$ is a correct parenthesis sequence. - It is formed by concatenating $A$ and $B$ in this order where $A$ and $B$ are non-empty correct parenthesis sequences. Given a string $S$ of length $N$ consisting of the characters $($ and $)$. For each $i$ where $0 \leq i \leq N$, define the string $T_i$ as the string obtained by concatenating the suffix of $S$ of length $N - i$ and the reversed string of the prefix of $S$ of length $i$, in this order. That is, if we denote the $i$-th character of $S$ as $S_i$, the string $T_i$ is formed by arranging the characters $S_{i+1}, S_{i+2}, \ldots, S_N, S_i, \ldots, S_2, S_1$ in sequence. For each $T_i$ where $0 \leq i \leq N$, solve the following problem: - Consider an operation where you replace one character in $T_i$ with either $($ or $)$. Find the minimum number of such operations required to make $T_i$ a correct parenthesis sequence.

The input is given in the following format: $$ \begin{aligned} &N \\ &S \end{aligned} $$ - $2 \leq N \leq 200,000$ - $N$ is even. - $S$ is a string of length $N$ consisting only of $($ and $)$.

Output $N + 1$ lines. On the $i + 1$-th line, output the answer for $T_i$.