D. Двухцветная ПСП
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Строка называется скобочной последовательностью, если она не содержит никаких символов, кроме «(» и «)». Скобочная последовательность называется правильной (кратко, ПСП), если из нее возможно получить корректное арифметическое выражение, вставляя символы «+» и «1». Например, «», «(())» и «()()» являются ПСП, а «)(» и «(()» не являются ПСП.

Легко заметить, что в ПСП каждой открывающей скобке ставится в пару некоторая закрывающая скобка. Используя данный факт, можно определить вложенность ПСП как максимальное количество пар скобок, таких, что $$$2$$$-я пара лежит внутри $$$1$$$-й, $$$3$$$-я — внутри $$$2$$$-й, и так далее. Например, вложенность «» равна $$$0$$$, «()()()» — $$$1$$$ и «()((())())» — $$$3$$$.

Теперь, вам задана ПСП $$$s$$$ четной длины $$$n$$$. Вам нужно покрасить каждую скобку $$$s$$$ в один из двух цветов: красный или синий. Скобочная последовательность $$$r$$$, состоящая только из красных скобок, должна быть ПСП, а также скобочная последовательность $$$b$$$, состоящая только из синих скобок, должна быть ПСП. Любая из них может быть пустой. Вам запрещается менять местами символы в $$$s$$$, $$$r$$$ или $$$b$$$. Все скобки должны быть покрашены.

Среди всех возможных вариантов вы должны выбрать такой, что минимизирует максимум из вложенности $$$r$$$ и $$$b$$$. Если существует несколько ответов, вы можете вывести любой.

Входные данные

В первой строке задано целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — длина ПСП $$$s$$$.

Во второй строке задана правильная скобочная последовательность $$$s$$$ ($$$|s| = n$$$, $$$s_i \in \{$$$«(», «)»$$$\}$$$).

Выходные данные

Выведите единственную строку $$$t$$$ длины $$$n$$$, состоящую из «0» и «1». Если $$$t_i$$$ равно «0», то символ $$$s_i$$$ принадлежит ПСП $$$r$$$, иначе $$$s_i$$$ принадлежит $$$b$$$.

Примеры
Входные данные
2
()
Выходные данные
11
Входные данные
4
(())
Выходные данные
0101
Входные данные
10
((()())())
Выходные данные
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$$$.