如果一个字符串不包含除“(”和“)”以外的任何字符,则该字符串称为括号序列。如果可以通过在该序列中插入字符“+”和“1”来获得正确的算术表达式,则该括号序列称为正则序列(简称为RBS)。例如,“”、“(())”和“()()”是 RBS,而“)(”和“(()”则不是。
我们可以看到,RBS 中的每个左括号都与一些右括号配对,并且利用这一事实,我们可以将 RBS 的嵌套深度定义为括号对的最大数量,使得 $$$2$$$-nd 对位于 $$$1$$$-st 内,$$$3$$$-rd 位于 $$$2$$$-nd 内,依此类推。例如,“”的嵌套深度为$$$0$$$,“()()()”为$$$1$$$,“()((())())”为$$$3$$$。
现在,您将获得偶数长度 $$$n$$$ 的 RBS $$$s$$$。您应该将 $$$s$$$ 的每个括号着色为两种颜色之一:红色或蓝色。仅由红色括号组成的括号序列 $$$r$$$ 应为 RBS,仅由蓝色括号 $$$b$$$ 组成的括号序列应为 RBS。其中任何一个都可以为空。不允许对 $$$s$$$、$$$r$$$ 或 $$$b$$$ 中的字符重新排序。任何括号都不能不着色。
在所有可能的变体中,您应该选择一种能够最小化 $$$r$$$ 和 $$$b$$$ 嵌套深度最大值的变体。如果有多个解决方案,您可以打印其中任何一个。
输入
第一行包含一个偶数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — RBS $$$s$$$ 的长度。
第二行包含常规括号序列 $$$s$$$ ($$$|s| = n$$$, $$$s_i \in \{$$$"(", ")"$$$\}$$$)。
输出
打印由“0”和“1”组成的长度为 $$$n$$$ 的单个字符串 $$$t$$$。如果 $$$t_i$$$ 等于 0,则字符 $$$s_i$$$ 属于 RBS $$$r$$$,否则 $$$s_i$$$ 属于 $$$b$$$。
示例
输入 #1
2 ()
输出 #1
11
输入 #2
4 (())
输出 #2
0101
输入 #3
10 ((()())())
输出 #3
0110001111
注意
在第一个示例中,最佳解决方案之一是 $$$s = $$$ "$$$\color{blue}{()}$$$"。 $$$r$$$ 为空,$$$b = $$$ "$$$()$$$"。答案是 $$$\max(0, 1) = 1$$$。
在第二个示例中,最佳做法是 $$$s = $$$ "$$$\color{red}{(}\color{blue}{(}\color{red}{)}\color{blue}{)}$$$"。 $$$r = b = $$$ "$$$()$$$" 答案是$$$1$$$。
在第三个例子中,我们可以使 $$$s = $$$ "$$$\color{red}{(}\color{blue}{((}\color{red}{)()}\color{blue}{)())}$$$"。 $$$r = $$$ "$$$()()$$$" 和 $$$b = $$$ "$$$(()())$$$" 答案是 $$$2$$$。