Bicolored RBS
Contest: Educational Codeforces Round 65 (Rated for Div. 2)
Difficulty rating: 1500
Tags: constructive algorithms, greedy

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.

Input format:
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 \{$$$"(", ")"$$$\}$$$).

Output format:
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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
2
()

Example output:
11

Example input:
4
(())

Example output:
0101

Editorial:
Let $$$d(s)$$$ be nested depth of RBS $$$s$$$. There is an interesting fact that $$$\max(d(r), d(b)) \ge \left\lceil \frac{d(s)}{2} \right\rceil$$$. From the other side we can always reach equation $$$\max(d(r), d(b)) = \left\lceil \frac{d(s)}{2} \right\rceil$$$ using some approaches.
Let's look at prefix of length $$$i$$$ of string $$$s$$$. Let $$$o_s(i)$$$ be number of opening bracket in the prefix, $$$c_s(i)$$$ — number of closing brackets. Then we can define balance of the $$$i$$$-th prefix of $$$s$$$ as $$$bal_s(i) = o_s(i) - c_s(i)$$$.
The author's approach is next:
Let's define level of pair of brackets (matched in natural way) as $$$bal_s(i - 1)$$$, where $$$i$$$ is position of opening bracket of this pair. Then we will color in red all pairs with even level and in blue — with odd level.
—— Proof of $$$\max(d(r), d(b)) \ge \left\lceil \frac{d(s)}{2} \right\rceil$$$:
It can be shown that $$$d(s) = \max\limits_{1 \le i \le n}(bal_s(i))$$$ and exists such $$$pos$$$ that $$$d(s) = bal_s(pos)$$$.
After any coloring of $$$s$$$ we can define number of opening/closing red (blue) brackets of $$$pos$$$-th prefix of $$$s$$$ as $$$o_r(pos)$$$ ($$$o_b(pos)$$$) and $$$c_r(pos)$$$ ($$$c_b(pos)$$$) respectively. Since $$$o_s(pos) = o_r(pos) + o_b(pos)$$$ and $$$c_s(pos) = c_r(pos) + c_b(pos)$$$, then $$$$$$\max(bal_r(pos), bal_b(pos)) = \max(o_r(pos) - c_r(pos), bal_b(pos)) \\ = \max((o_s(pos) - o_b(pos)) - (c_s(pos) - c_b(pos)), bal_b(pos)) = \max((o_s(pos) - c_s(pos)) - (o_b(pos) - c_b(pos)), bal_b(pos)) \\ = \max(bal_s(pos) - bal_b(pos), bal_b(pos)) \ge \left\lceil \frac{bal_s(pos)}{2} \right\rceil = \left\lceil \frac{d(s)}{2} \right\rceil.$$$$$$
Finally, $$$$$$\max(d(a), d(b)) = \max(\max\limits_{1 \le i \le n}(bal_r(i)), \max\limits_{1 \le i \le n}(bal_b(i))) \\ = \max\limits_{1 \le i, j \le n}(\max(bal_r(i), bal_b(j))) \ge \max(bal_r(pos), bal_b(pos)) \ge \left\lceil \frac{d(s)}{2} \right\rceil$$$$$$