#215787. [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 , , in this order where is a correct parenthesis sequence.
• It is formed by concatenating and in this order where and are non-empty correct parenthesis sequences.

Given a string of length consisting of the characters and .

For each where , define the string as the string obtained by concatenating the suffix of of length and the reversed string of the prefix of of length , in this order. That is, if we denote the -th character of as , the string is formed by arranging the characters in sequence.

For each where , solve the following problem:

• Consider an operation where you replace one character in with either or . Find the minimum number of such operations required to make a correct parenthesis sequence.

The input is given in the following format:

• is even.
• is a string of length consisting only of and .

Output lines. On the -th line, output the answer for .

样例输入 1

4
()()

样例输出 1

0
2
2
2
2

样例输入 2

6
)))(((

样例输出 2

4
2
2
0
0
0
0

样例输入 3

8
)())())(

样例输出 3

3
1
3
1
1
1
1
1
1