题目描述

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:

• $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$.

4
()()

0
2
2
2
2

6
)))(((

4
2
2
0
0
0
0

8
)())())(

3
1
3
1
1
1
1
1
1