一个合法括号序列是满足以下任意条件的字符串：

• 它是一个空字符串。
• 它由依次拼接 '('、$A$、')' 构成，其中 $A$ 是一个合法括号序列。
• 它由拼接 $A$ 和 $B$ 构成，其中 $A$ 和 $B$ 都是合法括号序列。

给你一个长度为 $n$ 且仅由字符 '(' 和 ')' 组成的字符串 $s$。

对于每个满足 $0 \le i \le n$ 的 $i$，定义 $t_i$ 为将 $s$ 长度为 $n-i$ 的后缀与 $s$ 长度为 $i$ 的翻转前缀依次拼接得到的字符串。也就是说，如果我们用 $s_i$ 表示 $s$ 的第 $i$ 个字符，那么字符串 $t_i$ 是由字符 $s_{i+1}, s_{i+2}, \dots, s_n, s_i, \dots, s_2, s_1$ 依次排列构成的。

对于每个满足 $0 \le i \le n$ 的 $t_i$，解决以下问题：考虑一种操作，你可以将 $t_i$ 中的一个字符替换为 '(' 或 ')'。求将 $t_i$ 变为合法括号序列所需的最小操作次数。

输入格式

输入的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$，$n$ 为偶数）。

第二行包含一个长度为 $n$ 且仅由 '(' 和 ')' 组成的字符串 $s$。

输出格式

输出 $n + 1$ 行。在第 $i + 1$ 行，输出 $t_i$ 的答案。

样例

输入 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