CF1167D.Bicolored RBS

A string is called bracket sequence if it does not contain any characters other than "(" and ")". A bracket sequence is called regular (shortly, RBS) if it is possible to obtain correct arithmetic expression by inserting characters "+" and "1" into this sequence. For example, "", "(())" and "()()" are RBS and ")(" and "(()" are not.

We can see that each opening bracket in RBS is paired with some closing bracket, and, using this fact, we can define nesting depth of the RBS as maximum number of bracket pairs, such that the $2$-nd pair lies inside the $1$-st one, the $3$-rd one — inside the $2$-nd one and so on. For example, nesting depth of "" is $0$, "()()()" is $1$ and "()((())())" is $3$.

Now, you are given RBS $s$ of even length $n$. You should color each bracket of $s$ into one of two colors: red or blue. Bracket sequence $r$, consisting only of red brackets, should be RBS, and bracket sequence, consisting only of blue brackets $b$, should be RBS. Any of them can be empty. You are not allowed to reorder characters in $s$, $r$ or $b$. No brackets can be left uncolored.

Among all possible variants you should choose one that minimizes maximum of $r$'s and $b$'s nesting depth. If there are multiple solutions you can print any of them.

如果一个字符串仅由字符 "(" 和 ")" 构成，则称其为括号序列。若能在该序列中插入字符 "+" 和 "1"，从而得到一个合法的算术表达式，则称该括号序列为正则括号序列（简称 RBS）。例如，""、"(())" 和 "()()" 是 RBS，而 ")(" 和 "((" 不是。

我们可以观察到：在任意 RBS 中，每个左括号都恰好与某个右括号配对。利用这一性质，可定义 RBS 的嵌套深度为：满足“第 $2$ 对括号完全位于第 $1$ 对括号内部，第 $3$ 对括号完全位于第 $2$ 对括号内部，……”的最大括号对数。例如，"" 的嵌套深度为 $0$，"()()()" 的嵌套深度为 $1$，而 "()((())())" 的嵌套深度为 $3$。

现在，你被给定一个长度为偶数 $n$ 的 RBS $s$。你需要将 $s$ 中的每个括号染成两种颜色之一：红色或蓝色。仅由红色括号按原顺序构成的字符串 $r$ 必须是 RBS；仅由蓝色括号按原顺序构成的字符串 $b$ 也必须是 RBS。$r$ 或 $b$ 均可为空。你不允许重新排列 $s$、$r$ 或 $b$ 中的字符，且 $s$ 中所有括号都必须被染色（不能遗漏）。

在所有可能的染色方案中，你需要选择一种，使得 $\max(\text{depth}(r),\ \text{depth}(b))$ 最小。若存在多种最优解，输出任意一种即可。

The first line contains an even integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of RBS $s$.

The second line contains regular bracket sequence $s$ ($|s| = n$, s_i \in {"(", ")"}).

第一行包含一个偶数 $n$（$2 \le n \le 2 \cdot 10^5$）——即 RBS $s$ 的长度。

第二行包含一个合法括号序列 $s$（$|s| = n$，且 s_i \in \{"(", "\)"\}）。

Print single string $t$ of length $n$ consisting of "0"-s and "1"-s. If $t_i$ is equal to 0 then character $s_i$ belongs to RBS $r$, otherwise $s_i$ belongs to $b$.

输出一个长度为 $n$ 的字符串 $t$，该字符串仅由字符 "0" 和 "1" 组成。如果 $t_i$ 等于 0，则字符 $s_i$ 属于括号序列 $r$；否则（即 $t_i = 1$），$s_i$ 属于 $b$。

In the first example one of optimal solutions is $s = $ "$\color{blue}{()}$". $r$ is empty and $b = $ "$()$". The answer is $\max(0, 1) = 1$.

In the second example it's optimal to make $s = $ "$\color{red}{(}\color{blue}{(}\color{red}{)}\color{blue}{)}$". $r = b = $ "$()$" and the answer is $1$.

In the third example we can make $s = $ "$\color{red}{(}\color{blue}{((}\color{red}{)()}\color{blue}{)())}$". $r = $ "$()()$" and $b = $ "$(()())$" and the answer is $2$.

在第一个例子中，一个最优解是 $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$。