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

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

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


-----Examples-----
Input
2
()

Output
11

Input
4
(())

Output
0101

Input
10
((()())())

Output
0110001111


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

Source: codeforces | Difficulty: MEDIUM
Tags: Greedy algorithms

Constructive algorithms


Solutions:
n = int(input())
s = input()
(red, blue) = (0, 0)
ans = [0 for _ in range(n)]
for (i, item) in enumerate(s):
	if item == '(':
		if red == blue:
			red += 1
			ans[i] = 0
		else:
			blue += 1
			ans[i] = 1
	elif item == ')':
		if red == blue:
			blue -= 1
			ans[i] = 1
		else:
			red -= 1
			ans[i] = 0
print(''.join(list(map(str, ans))))


n = int(input())
r = input()
g = 0
printString = ''
for i in range(n):
	if r[i] == '(':
		printString = printString + str(g % 2)
		g += 1
	else:
		printString = printString + str((g + 1) % 2)
		g -= 1
print(printString)


import sys

def get_array():
	return list(map(int, sys.stdin.readline().split()))

def get_ints():
	return map(int, sys.stdin.readline().split())

def input():
	return sys.stdin.readline().strip()

def main():
	n = int(input())
	s = input().strip()
	ans = [0] * n
	ans[0] = 0
	f = 0
	for i in range(1, n):
		if s[i] == s[i - 1]:
			f = 1 - f
		ans[i] = f
	print(*ans, sep='')

def __starting_point():
	main()
__starting_point()


n = int(input())
strng = input().strip()
lst1 = list(strng)
count = 0
lst2 = []
lst3 = []
for i in lst1:
	if i == '(':
		lst2.append(count)
		count += 1
	else:
		count -= 1
		lst2.append(count)
for k in lst2:
	if k % 2 == 0:
		lst3.append('0')
	else:
		lst3.append('1')
print(''.join(lst3))


def color(rbs, bin):
	opened = 0
	for i in range(len(rbs)):
		if rbs[i] == ')' and opened % 2 == 1:
			bin[i] = '1'
			opened -= 1
		elif rbs[i] == '(' and opened % 2 == 0:
			bin[i] = '1'
			opened += 1
		elif rbs[i] == '(':
			opened += 1
		elif rbs[i] == ')':
			opened -= 1
n = int(input())
bin = ['0'] * n
rbs = input()
color(rbs, bin)
print(''.join(bin))


n = int(input())
a = input()
cnt = 0
cnt2 = 0
for i in a:
	if i == '(':
		cnt += 1
		if cnt % 2:
			print(0, end='')
		else:
			print(1, end='')
	else:
		cnt2 += 1
		if cnt2 % 2:
			print(0, end='')
		else:
			print(1, end='')


n = int(input())
s = input()
a = 0
b = 0
p = ''
q = ''
ans = ''
for i in range(n):
	if s[i] == '(':
		if a > b:
			ans += '1'
			b += 1
		else:
			ans += '0'
			a += 1
	elif s[i] == ')':
		if a > b:
			ans += '0'
			a -= 1
		else:
			ans += '1'
			b -= 1
print(ans)


import itertools
import operator
n = int(input())
s = input().strip()
a = list(map(lambda u: 1 if u == '(' else -1, s))
b = list(itertools.accumulate(a))
maxb = max(b)
ans = list(map(lambda i: int(b[i] + (s[i] == ')') << 1 > maxb), [i for i in range(n)]))
print(''.join(map(str, ans)))


n = int(input())
line = input()
(a, b) = (0, 0)
for i in line:
	if i == '(':
		print(a, end='')
		a ^= 1
	if i == ')':
		print(b, end='')
		b ^= 1


n = int(input())
l = input()
r = 0
b = 0
maxb = 0
for j in range(n):
	if l[j] == '(':
		if r > b:
			b += 1
			print('1', end='')
		else:
			r += 1
			print('0', end='')
	elif r < b:
		b -= 1
		print('1', end='')
	else:
		r -= 1
		print('0', end='')
print()


n = int(input())
s = input()
bal = 0
for c in s:
	if c == ')':
		bal -= 1
	print(bal & 1, end='')
	if c == '(':
		bal += 1


n = int(input())
s = input()
d = 0
cnt = 0
for i in range(n):
	if s[i] == '(':
		cnt += 1
	else:
		cnt -= 1
	d = max(d, cnt)
cnt = 0
ans = ''
d = d // 2
for i in range(n):
	if s[i] == '(':
		cnt += 1
		if cnt <= d:
			ans += '0'
		else:
			ans += '1'
	else:
		if cnt <= d:
			ans += '0'
		else:
			ans += '1'
		cnt -= 1
print(ans)


n = int(input())
s = input()
color = 0
print(color, end='')
for i in range(1, n):
	if s[i] == s[i - 1]:
		color = 1 - color
	print(color, end='')
print()


def solution():
	input()
	sequence = input()
	ro = 0
	bo = 0
	ans = []
	for s in sequence:
		if s == '(':
			if ro <= bo:
				ans.append('1')
				ro += 1
				continue
			else:
				ans.append('0')
				bo += 1
			continue
		if ro >= bo:
			ans.append('1')
			ro -= 1
		else:
			ans.append('0')
			bo -= 1
	print(''.join(ans))
solution()


n = int(input())
x = list(input())
res = []
flag = True
for j in x:
	if j == '(':
		res.append('0' if flag else '1')
		flag = not flag
	else:
		flag = not flag
		res.append('0' if flag else '1')
print(''.join(res))


import sys
RI = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
n = int(ri())
st = ri()
dep = 0
maxdep = 0
for i in range(len(st)):
	if st[i] == '(':
		dep += 1
		maxdep = max(maxdep, dep)
	else:
		dep -= 1
con = maxdep // 2
dep = 0
ans = [-1] * len(st)
for i in range(len(st)):
	if st[i] == '(':
		dep += 1
		if dep > con:
			ans[i] = 1
		else:
			ans[i] = 0
	else:
		if dep > con:
			ans[i] = 1
		else:
			ans[i] = 0
		dep -= 1
print(''.join(map(str, ans)))


n = int(input())
a = input()
x = 1
y = 1
for i in a:
	if i == '(':
		print(x, end='')
		x ^= 1
	else:
		print(y, end='')
		y ^= 1


n = int(input())
s = str(input())
cum = [0] * (n + 1)
depth = [0] * (n + 1)
for i in range(n):
	if s[i] == '(':
		cum[i + 1] = cum[i] + 1
		depth[i + 1] = cum[i + 1]
	else:
		depth[i + 1] = cum[i]
		cum[i + 1] = cum[i] - 1
ans = ['0'] * n
for i in range(n):
	if depth[i + 1] % 2 == 0:
		ans[i] = '0'
	else:
		ans[i] = '1'
print(''.join(ans))


n = int(input())
s = input()
(a, b) = (0, 0)
color = [-1] * n
for (i, c) in enumerate(s):
	if c == '(':
		if a < b:
			a += 1
			color[i] = 0
		else:
			b += 1
			color[i] = 1
	elif c == ')':
		if a < b:
			b -= 1
			color[i] = 1
		else:
			a -= 1
			color[i] = 0
print(*color, sep='')


def main():
	from sys import stdin, stdout

	def read():
		return stdin.readline().rstrip('\n')

	def read_array(sep=None, maxsplit=-1):
		return read().split(sep, maxsplit)

	def read_int():
		return int(read())

	def read_int_array(sep=None, maxsplit=-1):
		return [int(a) for a in read_array(sep, maxsplit)]

	def write(*args, **kwargs):
		sep = kwargs.get('sep', ' ')
		end = kwargs.get('end', '\n')
		stdout.write(sep.join((str(a) for a in args)) + end)

	def write_array(array, **kwargs):
		sep = kwargs.get('sep', ' ')
		end = kwargs.get('end', '\n')
		stdout.write(sep.join((str(a) for a in array)) + end)
	n = read_int()
	s = read()[:n]
	bal0 = bal1 = 0
	out = []
	for ch in s:
		if ch == '(':
			if bal0 < bal1:
				out.append('0')
				bal0 += 1
			else:
				out.append('1')
				bal1 += 1
		elif bal0 > bal1:
			out.append('0')
			bal0 -= 1
		else:
			out.append('1')
			bal1 -= 1
	write(''.join(out))
main()


n = int(input())
str = input()
tmp = 0
ans = ''
for i in range(len(str)):
	if str[i] == '(':
		if str[i - 1] == '(':
			tmp += 1
	elif str[i - 1] != '(':
		tmp -= 1
	if tmp % 2 == 1:
		ans += '1'
	else:
		ans += '0'
print(ans)


import sys, math, queue
MOD = 10 ** 9 + 7
n = int(input())
s = input()
col = [None for i in range(n)]
s0 = 0
s1 = 0
for i in range(n):
	if s[i] == '(':
		if s0 == 0:
			s0 += 1
			col[i] = '0'
		elif s1 == 0:
			s1 += 1
			col[i] = '1'
		elif s0 < s1:
			s0 += 1
			col[i] = '0'
		else:
			s1 += 1
			col[i] = '1'
	elif s0 != 0:
		s0 -= 1
		col[i] = '0'
	else:
		s1 -= 1
		col[i] = '1'
print(''.join(col))


n = int(input())
s = input()
res = ''
(op, cl) = (0, 0)
for brct in s:
	if brct == '(':
		op += 1
		res += str(op % 2)
	else:
		cl += 1
		res += str(cl % 2)
print(res)


n = int(input())
s = input()
red = 0
blue = 0
out = ''
for c in s:
	if c == '(':
		if red < blue:
			red += 1
			out += '0'
		else:
			blue += 1
			out += '1'
	elif red < blue:
		blue -= 1
		out += '1'
	else:
		red -= 1
		out += '0'
print(out)


import itertools
import bisect
import math
from collections import *
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(10 ** 5)
ii = lambda : int(input())
lmii = lambda : list(map(int, input().split()))
slmii = lambda : sorted(map(int, input().split()))
li = lambda : list(input())
mii = lambda : map(int, input().split())
msi = lambda : map(str, input().split())

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def ncr(n, r):
	return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def npr(n, r):
	return math.factorial(n) // math.factorial(n - r)

def main():
	n = ii()
	s = li()
	cnt = 0
	mx = 0
	for i in range(n):
		if s[i] == '(':
			cnt += 1
		else:
			mx = max(mx, cnt)
			cnt -= 1
	ele = math.ceil(mx / 2)
	cnt = 0
	for i in range(n):
		if s[i] == '(':
			if cnt < ele:
				cnt += 1
				print('1', end='')
			else:
				print('0', end='')
		elif cnt > 0:
			cnt -= 1
			print('1', end='')
		else:
			print('0', end='')
	print()
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input())
s = input()
i = 0
r = 0
b = 0
ans = ''
for i in range(len(s)):
	if s[i] == '(':
		if r <= b:
			r += 1
			ans = ans + '0'
		else:
			b += 1
			ans = ans + '1'
	elif r >= b:
		r -= 1
		ans = ans + '0'
	else:
		b -= 1
		ans = ans + '1'
print(ans)


n = int(input())
s = input()
nesting_depth = 0
current_depth = 0
for c in s:
	current_depth += 1 if c == '(' else -1
	nesting_depth = max(nesting_depth, current_depth)
ans = ['0'] * n
i = 0
for c in s:
	if c == '(':
		current_depth += 1
		if current_depth > nesting_depth // 2:
			ans[i] = '1'
	else:
		if current_depth > nesting_depth // 2:
			ans[i] = '1'
		current_depth -= 1
	i += 1
print(''.join(ans))


def gns():
	return [int(x) for x in input().split()]
n = int(input())
s = input()
d = 0
for c in s:
	if c == '(':
		d += 1
		print(d % 2, end='')
	else:
		print(d % 2, end='')
		d -= 1
print()


n = int(input())
s = input()
(a, b) = (0, 0)
ans = ''
for x in s:
	if x == '(':
		ans += str(a)
		a ^= 1
	else:
		ans += str(b)
		b ^= 1
print(ans)


(n, s) = (int(input()), input())
(be, en) = (1, 1)
for i in s:
	if i == '(':
		print(be, end='')
		be ^= 1
	else:
		print(en, end='')
		en ^= 1


n = int(input())
a = input()
s = []
b = 0
c = 0
for i in a:
	if i == ')':
		if b > c:
			b -= 1
			s.append('1')
		else:
			s.append('0')
			c -= 1
	elif b < c:
		b += 1
		s.append('1')
	else:
		s.append('0')
		c += 1
print(''.join(s))


input()
s = input()
ans = ''
cnt1 = 0
cnt2 = 0
for i in s:
	if i == ')':
		if cnt2 % 2:
			ans += '1'
		else:
			ans += '0'
		cnt2 += 1
	else:
		if cnt1 % 2:
			ans += '1'
		else:
			ans += '0'
		cnt1 += 1
print(ans)


n = int(input())
s = input()
c = 0
for i in range(n):
	if s[i] == '(':
		c += 1
		if c % 2 == 1:
			print('0', end='')
		else:
			print('1', end='')
	else:
		if c % 2 == 1:
			print('0', end='')
		else:
			print('1', end='')
		c -= 1


n = int(input())
st = input()
ans = [0] * n
r = []
s = []
for i in range(n):
	if st[i] == '(':
		if len(r) > len(s):
			s.append(st[i])
			ans[i] = '1'
		else:
			r.append(st[i])
			ans[i] = '0'
	elif len(r) > len(s):
		r.pop()
		ans[i] = '0'
	else:
		s.pop()
		ans[i] = '1'
print(''.join(ans))


from collections import deque
n = int(input())
s = input()
left = deque([])
ans = [-1] * n
flag = True
for i in range(n):
	if s[i] == '(':
		left.append(i)
	elif flag:
		l_idx = left.popleft()
		ans[l_idx] = 0
		ans[i] = 0
		flag = False
	else:
		l_idx = left.popleft()
		ans[l_idx] = 1
		ans[i] = 1
		flag = True
ans = list(map(str, ans))
print(''.join(ans))


n = int(input())
s = input()
a = 0
b = 0
res = ''
for i in range(n):
	if s[i] == '(':
		if a > b:
			b += 1
			res += '1'
		else:
			a += 1
			res += '0'
	elif a < b:
		b -= 1
		res += '1'
	else:
		a -= 1
		res += '0'
print(res)


n = int(input())
arr = list(input())
count = 0
maxcount = 0
for i in arr:
	if i == '(':
		count += 1
	else:
		count -= 1
	maxcount = max(maxcount, count)
toAchive = maxcount // 2
ans = ''
ActiveCount = 0
count = 0
for i in arr:
	if i == '(':
		if count < toAchive:
			ans += '1'
		else:
			ans += '0'
		count += 1
	else:
		count -= 1
		if count < toAchive:
			ans += '1'
		else:
			ans += '0'
print(ans)


n = int(input())
a = input()
ans = [0 for i in range(n)]
k = 0
for i in range(1, n):
	if a[i] == '(':
		ans[i] = k + 1
		k += 1
	else:
		ans[i] = k
		k -= 1
for x in ans:
	print(x % 2, end='')


n = int(input())
s = input()
indi1 = 'r'
indi2 = 'r'
ans = []
for i in s:
	if i == '(':
		if indi1 == 'r':
			ans.append('1')
			indi1 = 'b'
		else:
			ans.append('0')
			indi1 = 'r'
	elif indi2 == 'r':
		ans.append('1')
		indi2 = 'b'
	else:
		ans.append('0')
		indi2 = 'r'
s1 = ''.join(ans)
print(s1)


import sys
input = sys.stdin.readline
n = int(input())
s = input().strip()
clr = []
(s0, s1) = (0, 0)
for x in s:
	if x == '(':
		if s0 <= s1:
			s0 += 1
			clr.append(0)
		else:
			s1 += 1
			clr.append(1)
	elif s0 > s1:
		s0 -= 1
		clr.append(0)
	else:
		s1 -= 1
		clr.append(1)
print(''.join(map(str, clr)))


from sys import stdin, stdout
n = int(stdin.readline().strip())
s = stdin.readline().strip()
ans = ''
cd = -1
co = 0
cc = 0
for i in s:
	if i == '(':
		co += 1
	elif i == ')':
		co -= 1
	cd = max(cd, co)
div = cd // 2
cd = 1
if cd <= div:
	stdout.write('0')
else:
	stdout.write('1')
for i in range(1, len(s)):
	if s[i - 1] == '(':
		if s[i] == '(':
			cd += 1
	elif s[i] == ')':
		cd -= 1
	if cd <= div:
		stdout.write('0')
	else:
		stdout.write('1')
print(ans)


N = int(input())
s = input()
D = []
d = max_d = 0
for i in range(N):
	D.append(d)
	if s[i] == '(':
		d += 1
	else:
		d -= 1
	max_d = max(max_d, d)
D.append(d)
target_d = max_d // 2
answer = ''.join((str(int(D[i] <= target_d and D[i + 1] <= target_d)) for i in range(N)))
print(answer)


n = int(input())
s = input()
ans = ''
rstec = []
bstec = []
rc = 0
bc = 0
for i in s:
	if i == '(':
		if len(rstec) <= len(bstec):
			rstec.append('(')
			ans += '0'
		elif len(rstec) > len(bstec):
			bstec.append('(')
			ans += '1'
	elif i == ')':
		if len(rstec) == 0:
			ans += '1'
			bstec.pop()
		elif len(bstec) == 0:
			ans += '0'
			rstec.pop()
		elif len(rstec) >= len(bstec):
			ans += '0'
			rstec.pop()
		elif len(rstec) < len(bstec):
			ans += '1'
			bstec.pop()
print(ans)


n = int(input().split()[0])
s = list(map(str, input()))
res = ''
blue = 0
red = 0
for el in s:
	if el == '(':
		if red > blue:
			blue += 1
			res += '1'
		else:
			red += 1
			res += '0'
	elif el == ')':
		if red > blue:
			red -= 1
			res += '0'
		else:
			blue -= 1
			res += '1'
print(res)


import sys
input = sys.stdin.readline
n = int(input())
S = input().strip()
NOW = 0
LIST = []
for s in S:
	if s == '(':
		LIST.append(NOW)
		NOW += 1
	else:
		NOW -= 1
		LIST.append(NOW)
ANS = []
for l in LIST:
	if l % 2 == 0:
		ANS.append('0')
	else:
		ANS.append('1')
print(''.join(ANS))


n = int(input())
s = list(str(input()))
ans = ''
r = 0
b = 0
for i in s:
	if i == '(':
		if r <= b:
			r += 1
			ans += '0'
		else:
			b += 1
			ans += '1'
	elif r >= b:
		r -= 1
		ans += '0'
	else:
		b -= 1
		ans += '1'
print(ans)


n = int(input())
ad = 0
bd = 0

def out(x):
	print(x, end='')
for c in input():
	if c == '(':
		if ad > bd:
			bd += 1
			out(1)
		else:
			ad += 1
			out(0)
	elif ad > bd:
		ad -= 1
		out(0)
	else:
		bd -= 1
		out(1)
assert ad == bd == 0


import math
from decimal import Decimal

def na():
	n = int(input())
	b = [int(x) for x in input().split()]
	return (n, b)

def nab():
	n = int(input())
	b = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	return (n, b, c)

def dv():
	(n, m) = map(int, input().split())
	return (n, m)

def dva():
	(n, m) = map(int, input().split())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	return (n, m, b)

def eratosthenes(n):
	sieve = list(range(n + 1))
	for i in sieve:
		if i > 1:
			for j in range(i + i, len(sieve), i):
				sieve[j] = 0
	return sorted(set(sieve))

def nm():
	n = int(input())
	b = [int(x) for x in input().split()]
	m = int(input())
	c = [int(x) for x in input().split()]
	return (n, b, m, c)

def dvs():
	n = int(input())
	m = int(input())
	return (n, m)
n = int(input())
a = input()
ans = [0] * n
tc = 0
for i in range(1, n):
	if a[i] == '(':
		ans[i] = tc + 1
		tc += 1
	else:
		ans[i] = tc
		tc -= 1
for i in ans:
	print(i % 2, end='')


x = int(input())
s = input()
c = 1
d = 1
for i in range(0, x):
	if s[i] == '(':
		print(c, end='')
		c = 1 - c
	else:
		print(d, end='')
		d = 1 - d


n = input()
s = input()
o = ''
r_count = 0
b_count = 0
for i in s:
	if i == '(':
		if r_count > b_count:
			o += '1'
			b_count += 1
		else:
			o += '0'
			r_count += 1
	elif r_count > 0:
		o += '0'
		r_count -= 1
	else:
		o += '1'
		b_count -= 1
print(o)


n = int(input())
s = input()
l = [-1] * n
p = 0
d1 = 0
d2 = 0
for i in s:
	if i == '(':
		if d1 <= d2:
			d1 += 1
			l[p] = 0
		else:
			d2 += 1
			l[p] = 1
	elif d1 >= d2:
		d1 -= 1
		l[p] = 0
	else:
		d2 -= 1
		l[p] = 1
	p += 1
for i in l:
	print(i, end='')
print()


import sys

class DBicoloredRBS:

	def solve(self):
		n = int(input())
		s = input()
		d = 0
		res = [0] * n
		max_depth = 0
		for i in range(n):
			if s[i] == '(':
				d += 1
				max_depth = max(max_depth, d)
			else:
				d -= 1
		target = max_depth // 2
		d = 0
		i = 0
		while i < n:
			if s[i] == '(':
				if d + 1 > target:
					res[i] = 1
				d += 1
			else:
				if d > target:
					res[i] = 1
				d -= 1
			i += 1
		print(''.join((str(x) for x in res)))
solver = DBicoloredRBS()
input = sys.stdin.readline
solver.solve()


n = int(input())
s = input()
ans = ['0' for i in range(n)]
depth = 0
st = []
for i in range(n):
	if s[i] == '(':
		depth += 1
		st.append(i)
	else:
		val = 0
		if depth % 2 == 0:
			val = 1
		x = st[len(st) - 1]
		y = i
		st.pop()
		ans[x] = val
		ans[y] = val
		depth -= 1
print(''.join([str(i) for i in ans]))


n = int(input())
s = input()
d = 0
for c in s:
	if c == '(':
		d = d + 1
		print(d % 2, end='')
	else:
		print(d % 2, end='')
		d = d - 1
print()


input()
s = input()
l = '('
r = ')'
d = 0
a = []
pre = 0
for i in s:
	if i == l:
		if pre == l:
			d += 1
		pre = l
	else:
		if pre == r:
			d -= 1
		pre = r
	if d % 2 == 0:
		a += [1]
	else:
		a += [0]
for i in a:
	print(i, end='')


n = int(input())
A = input()
stack = []
for i in A:
	if i == '(':
		if len(stack) == 0 or stack[-1] == 1:
			stack.append(0)
			print(0, end='')
		else:
			stack.append(1)
			print(1, end='')
	else:
		print(stack[-1], end='')
		stack.pop()


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max

def main():
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	for _ in range(1):
		n = ri()
		s = rs()
		opind = []
		clind = []
		for i in range(n):
			if s[i] == '(':
				opind.append(i)
			else:
				clind.append(i)
		ans = ['0'] * n
		for i in range(0, n // 2, 2):
			ans[opind[i]] = '1'
			ans[clind[i]] = '1'
		print(''.join(ans))
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


import sys

def mul(xs):
	r = 1
	for x in xs:
		r *= x
	return r

class Main:

	def __init__(self):
		self.buff = None
		self.index = 0

	def next(self):
		if self.buff is None or self.index == len(self.buff):
			self.buff = self.next_line()
			self.index = 0
		val = self.buff[self.index]
		self.index += 1
		return val

	def next_line(self):
		return sys.stdin.readline().split()

	def next_ints(self):
		return [int(x) for x in sys.stdin.readline().split()]

	def next_int(self):
		return int(self.next())

	def solve(self):
		n = self.next_int()
		s = self.next()
		d = 0
		r = []
		for c in s:
			if c == '(':
				d += 1
				if d % 2 == 0:
					r.append(0)
				else:
					r.append(1)
			else:
				if d % 2 == 0:
					r.append(0)
				else:
					r.append(1)
				d -= 1
		print(''.join((str(x) for x in r)))
Main().solve()


n = int(input())
x = input()
cur = 0
ma = 0
for i in x:
	if i == '(':
		cur += 1
		ma = max(ma, cur)
	else:
		cur -= 1
ans = ['0'] * n
mi = ma // 2
for i in range(n):
	if x[i] == '(':
		if cur >= mi:
			ans[i] = '1'
		cur += 1
	else:
		cur -= 1
		if cur >= mi:
			ans[i] = '1'
print(''.join(ans))


n = int(input())
s = input()
wyn = 0
nr = 0
czer = 0
nieb = 0
for i in range(n):
	if s[i] == '(':
		if czer <= nieb:
			print('1', end='')
			czer += 1
		else:
			print('0', end='')
			nieb += 1
	if s[i] == ')':
		if czer <= nieb:
			print('0', end='')
			nieb -= 1
		else:
			print('1', end='')
			czer -= 1


from collections import deque
n = int(input())
s = input()
o = ['0'] * n
l = list(s)
stack = deque([])
cnt = 0
for i in range(len(l)):
	if l[i] == '(':
		stack.append(i)
	else:
		u = stack.popleft()
		if cnt % 2 == 0:
			o[u] = '0'
			o[i] = '0'
		else:
			o[u] = '1'
			o[i] = '1'
		cnt = cnt + 1
print(''.join(o))


n = int(input())
s = input()
a = 0
b = 0
for ch in s:
	if ch == '(':
		if a <= b:
			a += 1
			print(0, end='')
		else:
			b += 1
			print(1, end='')
	elif a >= b:
		a -= 1
		print(0, end='')
	else:
		b -= 1
		print(1, end='')


def depth(A):
	result = 0
	current = 0
	for i in range(len(A)):
		if A[i] == '(':
			current += 1
			result = max([result, current])
		else:
			current -= 1
	return result
n = int(input())
S = input()
S_d = depth(S)
result = [0] * len(S)
current = 0
for i in range(len(S)):
	if S[i] == '(':
		current += 1
	if current > S_d // 2:
		result[i] = 1
	else:
		result[i] = 0
	if S[i] == ')':
		current -= 1
print(''.join(map(str, result)))


from sys import stdin, stdout

def input():
	return stdin.readline()[:-1]
import math

class disjoint_set:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.size = [1] * n

	def union(self, a, b):
		p1 = self.find(a)
		p2 = self.find(b)
		if p1 == p2:
			return False
		if self.size[p1] > self.size[p2]:
			self.parent[p2] = p1
			self.size[p1] += self.size[p2]
		else:
			self.parent[p1] = p2
			self.size[p2] += self.size[p1]

	def find(self, x):
		ans = x
		while ans != self.parent[ans]:
			ans = self.parent[ans]
		temp = x
		while temp != self.parent[temp]:
			temp2 = self.parent[temp]
			self.parent[temp] = ans
			temp = temp2
		return ans
n = int(input())
s = input()
colour = [0] * n
max_depth = 0
curr_depth = 0
for i in range(n):
	if s[i] == '(':
		curr_depth += 1
	else:
		curr_depth -= 1
	if curr_depth > max_depth:
		max_depth = curr_depth
max_depth = math.ceil(max_depth / 2)
flag = False
curr_depth = 0
count = 0
for i in range(n):
	if s[i] == '(':
		curr_depth += 1
		if curr_depth > max_depth:
			count += 1
			colour[i] = 1
	if s[i] == ')':
		curr_depth -= 1
		if count > 0:
			colour[i] = 1
			count -= 1
for i in colour:
	print(i, end='')
print('')


input()
s = input()
red = blue = 0
result = ''
for c in s:
	if c == '(':
		if red > blue:
			result += '0'
			blue += 1
		else:
			result += '1'
			red += 1
	elif red > blue:
		result += '1'
		red -= 1
	else:
		result += '0'
		blue -= 1
print(result)


n = int(input())
s = input()
a = [0] * n
t = []
now = 0
for i in range(n):
	if s[i] == '(':
		now += 1
		t.append(i)
	else:
		a[i] = a[t[len(t) - 1]] = now % 2
		t.pop()
		now -= 1
for i in a:
	print(i, end='')


n = int(input().lstrip())
s = input().strip()
R_STEP = '0'
B_STEP = '1'
r = 0
b = 0
max_depth = 0
steps = []
for c in s:
	if c == '(':
		if r < b:
			r += 1
			steps.append(R_STEP)
		else:
			b += 1
			steps.append(B_STEP)
	if c == ')':
		if r < b:
			b -= 1
			steps.append(B_STEP)
		else:
			r -= 1
			steps.append(R_STEP)
	max_depth = max(max_depth, r, b)
print(''.join(steps))


input()
s = input()
r = b = 0
op = []
ans = []
for c in s:
	if c == '(':
		if r <= b:
			op.append(False)
			r += 1
			ans.append('0')
		else:
			op.append(True)
			b += 1
			ans.append('1')
	elif op.pop():
		b -= 1
		ans.append('1')
	else:
		r -= 1
		ans.append('0')
print(''.join(ans))


import os
from io import BytesIO, IOBase
import sys
from collections import defaultdict, deque, Counter
from math import sqrt, pi, ceil, log, inf, gcd, floor
from itertools import combinations, permutations
from bisect import *
from fractions import Fraction

def main():
	n = int(input())
	a = input().rstrip()
	(s, f, ans) = (deque(), 0, [0] * n)
	for i in range(n):
		if a[i] == '(':
			s.append(i)
		elif len(s):
			z = s.popleft()
			if f:
				ans[z] = f
				ans[i] = f
			else:
				ans[z] = f
				ans[i] = f
			f = int(not f)
	print(*ans, sep='')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input())
s = input()
flag_open = 0
flag_close = 0
res = []
for i in s:
	if i == '(':
		res.append(flag_open)
		if flag_open == 0:
			flag_open = 1
		else:
			flag_open = 0
	if i == ')':
		res.append(flag_close)
		if flag_close == 0:
			flag_close = 1
		else:
			flag_close = 0
for i in res:
	print(i, end='')
print()


from sys import stdin, stdout
import math, queue, heapq
fastinput = stdin.readline
fastout = stdout.write

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def computeLPSArray(pat, M, lps):
	len = 0
	lps[0]
	i = 1
	while i < M:
		if pat[i] == pat[len]:
			len += 1
			lps[i] = len
			i += 1
		elif len != 0:
			len = lps[len - 1]
		else:
			lps[i] = 0
			i += 1
t = 1
while t:
	t -= 1
	n = int(fastinput())
	s = input()
	toopen = 1
	toclose = 1
	ans = []
	for i in s:
		if i == '(':
			ans.append(toopen)
			if toopen == 1:
				toopen = 0
			else:
				toopen = 1
		else:
			ans.append(toclose)
			if toclose == 1:
				toclose = 0
			else:
				toclose = 1
	for i in ans:
		print(i, end='')


import sys
input = sys.stdin.readline
n = int(input())
s = input().split()[0]
red = 0
blue = 0
mx = 0
res = ['0'] * n
for i in range(n):
	if s[i] == '(':
		if red > blue:
			blue += 1
			res[i] = '1'
		else:
			red += 1
		mx = max(mx, red, blue)
	elif red >= blue:
		red -= 1
	else:
		blue -= 1
		res[i] = '1'
print(''.join(res))


input()
brackets = list(input())
a = 0
b = 0
result = []
for bracket in brackets:
	if bracket == '(':
		if a == b:
			a += 1
			result.append('1')
		else:
			b += 1
			result.append('0')
	elif a > b:
		a -= 1
		result.append('1')
	else:
		b -= 1
		result.append('0')
print(''.join(result))


n = int(input())
s = input()
(stack, ko, kc, answer) = ([], 0, 0, [None for _ in range(n)])
for i in range(n):
	if not stack:
		stack.append(s[i])
		answer[i] = ko
		ko = 1 - ko
	elif stack[-1] == s[i]:
		stack.append(s[i])
		answer[i] = ko
		ko = 1 - ko
	else:
		stack.pop()
		answer[i] = kc
		kc = 1 - kc
print(''.join(map(str, answer)))


len = int(input())
str = input()
(r, b) = (0, 0)
ans = []
for x in str:
	if x == '(':
		if r <= b:
			ans.append('0')
			r += 1
		else:
			ans.append('1')
			b += 1
	elif r >= b:
		ans.append('0')
		r -= 1
	else:
		ans.append('1')
		b -= 1
print(*ans, sep='')


n = int(input())
a = input()
(stack, ans) = ([], [])
for q in range(len(a)):
	if a[q] == ')':
		ans.append(stack.pop())
	elif len(stack) > 0 and stack[-1] == '0':
		stack.append('1')
		ans.append('1')
	else:
		stack.append('0')
		ans.append('0')
print(''.join(ans))


import math
from collections import deque

def color_the_string(n, given_string):
	depth_counter = 0
	colored_string = ''
	for index in range(len(given_string)):
		char = given_string[index]
		if char == '(':
			depth_counter += 1
			if depth_counter % 2 == 0:
				colored_string += '0'
			else:
				colored_string += '1'
		else:
			if depth_counter % 2 == 0:
				colored_string += '0'
			else:
				colored_string += '1'
			depth_counter -= 1
	return colored_string
n = int(input())
bicolor_sequence = input()
print(color_the_string(n, bicolor_sequence))


n = int(input().strip())
s = input().strip()
a = 0
for i in range(n):
	if s[i] == '(':
		if a & 1:
			print(0, end='')
		else:
			print(1, end='')
		a += 1
	else:
		a -= 1
		if a & 1:
			print(0, end='')
		else:
			print(1, end='')


n = input()
s = input()
depth = 0
out = []
for c in s:
	if c == '(':
		out.append(str(depth % 2))
		depth += 1
	else:
		depth -= 1
		out.append(str(depth % 2))
print(''.join(out))


n = int(input())
RBS = input()
depth = 0
for char in RBS:
	if char == '(':
		depth += 1
		print(depth % 2, end='')
	elif char == ')':
		depth -= 1
		print((depth + 1) % 2, end='')
print('')


n = int(input())
s = input()
d = 0
l = []
for c in s:
	if c == '(':
		l.append(d)
		d ^= 1
	else:
		d ^= 1
		l.append(d)
print(''.join([str(i) for i in l]))


import sys
import math
import collections
from pprint import pprint as pp
mod = 1000000007

def vector(size, val=0):
	vec = [val for i in range(size)]
	return vec

def matrix(rowNum, colNum, val=0):
	mat = []
	for i in range(rowNum):
		collumn = [val for j in range(colNum)]
		mat.append(collumn)
	return mat
(n, s) = (int(input()), input())
ans = vector(n)
op = 0
cl = 0
for i in range(n):
	if s[i] == '(':
		ans[i] = op
		op ^= 1
	else:
		ans[i] = cl
		cl ^= 1
for i in ans:
	print(i, end='')


def main():
	n = int(input())
	s = input()
	ans = ''
	red = 0
	blue = 0
	for i in range(n):
		if s[i] == '(':
			if red <= blue:
				red += 1
				ans += '0'
			else:
				blue += 1
				ans += '1'
		elif blue > red:
			blue -= 1
			ans += '1'
		else:
			red -= 1
			ans += '0'
	print(ans)
main()


input()
s = input()
res = [0] * len(s)
r = b = 0
for (i, c) in enumerate(s):
	if c == '(':
		if r < b:
			r += 1
		else:
			b += 1
			res[i] = 1
	elif r > b:
		r -= 1
	else:
		b -= 1
		res[i] = 1
print(''.join(map(str, res)))


n = int(input())
S = input()
Max = 0
s = []
d = {}
for (i, str) in enumerate(S):
	if str == '(':
		s.append([str, i])
	elif str == ')':
		num = 0
		while len(s[-1]) == 1:
			p = s.pop()[0]
			num = max(p, num)
		pair = s.pop()
		if num + 1 not in d:
			d[num + 1] = []
		d[num + 1].append([pair[1], i])
		Max = max(Max, num + 1)
		s.append([num + 1])
choose = ['0'] * n
thres = Max // 2
for (k, v) in d.items():
	if k > thres:
		for p in v:
			choose[p[0]] = '1'
			choose[p[1]] = '1'
print(''.join(choose))


import math as mt
n = int(input())
s = input()
l = []
ans = [-1] * n
cnt = 0
l1 = []
maxi = 0
for i in range(n):
	if s[i] == ')':
		l.pop()
		cnt += 1
	else:
		l.append(i)
		maxi = max(maxi, len(l))
		cnt = 0
cnt = 0
if maxi % 2 != 0:
	maxi += 1
l1 = []
ind = 0
for i in range(n):
	if s[i] == ')':
		x = l1.pop()
		ans[x] = ind
		ans[i] = ind
		if len(l1) <= maxi // 2:
			ind = 0
	else:
		l1.append(i)
		if len(l1) > maxi // 2:
			ind = 1
print(*ans, sep='')


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().decode().rstrip('\n\r')
from collections import deque as dq
mod = 10 ** 9 + 7
Cases = 1
for Case in range(Cases):
	n = ri()
	s = rs()
	stack = dq()
	num = 0
	ans = ''
	for i in s:
		if i == '(':
			stack.append(num)
			print(num, end='')
			num = 1 - num
		else:
			print(stack.popleft(), end='')


def get_num():
	return int(input())

def print_arr(arr: list):
	for val in arr:
		print(val)

def read_num_list():
	num_str = input()
	return [int(v) for v in num_str.split(' ')]

def read_nums(k):
	lst = []
	for _ in range(k):
		lst.append(get_num())
	return lst
n = get_num()
s = input()
labels = []
l_str = ''
r_str = ''
l_depth = 0
r_depth = 0
for paren in s:
	if paren == '(':
		if l_depth <= r_depth:
			l_depth += 1
			labels.append(0)
		else:
			r_depth += 1
			labels.append(1)
	elif l_depth > r_depth:
		l_depth -= 1
		labels.append(0)
	else:
		r_depth -= 1
		labels.append(1)
print(''.join([str(x) for x in labels]))


n = int(input())
s = input()
count = 0
li = []
for i in range(0, n):
	if s[i] == '(':
		li.append(i % 2)
		print(i % 2, end='')
	else:
		print(li[-1], end='')
		li.pop(-1)


def bicolored_rbs(s):
	red = 0
	blue = 0
	result = ''
	for current in s:
		if current == '(':
			if red < blue:
				red = red + 1
				result = result + '0'
			else:
				blue = blue + 1
				result = result + '1'
		if current == ')':
			if red > blue:
				red = red - 1
				result = result + '0'
			else:
				blue = blue - 1
				result = result + '1'
	return result
length = input()
s = input()
print(bicolored_rbs(s))


n = int(input())
s = input()
ans = []
l = 0
for i in range(n):
	if s[i] == '(':
		l += 1
		ans.append(l % 2)
	if s[i] == ')':
		ans.append(l % 2)
		l -= 1
print(''.join([str(i) for i in ans]))


n = int(input())
s = input()
count = {0: 0, 1: 0}
r = []
for c in s:
	if c == '(':
		binn = min(count.items(), key=lambda p: p[1])
		count[binn[0]] += 1
		r.append(binn[0])
	else:
		binn = max(count.items(), key=lambda p: p[1])
		count[binn[0]] -= 1
		r.append(binn[0])
print(''.join([str(c) for c in r]))


n = int(input())
s = input()
stack = []
queue = []
ans = [-1] * n
old = 0
new = 0
flag = 0
for i in range(n):
	if s[i] == '(':
		if len(stack) == 0:
			stack.append(s[i])
			old = i
		else:
			queue.append([i, s[i]])
	elif s[i] == ')':
		stack.pop()
		ans[i] = flag
		ans[old] = flag
		if flag == 0:
			flag = 1
		else:
			flag = 0
	if len(stack) == 0:
		if len(queue) > 0:
			old = queue[0][0]
			stack.append(queue.pop(0)[1])
sol = ''
for i in ans:
	if i == 0:
		sol += '0'
	else:
		sol += '1'
print(sol)


n = int(input())
s = input()
v = 0
v_m = 0
for i in range(n):
	if s[i] == '(':
		v += 1
		if v_m < v:
			v_m = v
	else:
		v -= 1
possible_v = v_m // 2
answer = ''
last = '0'
r = 0
b = 0
for i in range(n):
	if s[i] == '(':
		if r < possible_v:
			r += 1
			answer += '0'
		else:
			b += 1
			answer += '1'
	elif r <= possible_v and b > 0:
		b -= 1
		answer += '1'
	else:
		r -= 1
		answer += '0'
print(answer)


n = int(input())
s = input()
a = ''
count = 0
for i in range(n):
	if s[i] == ')':
		count -= 1
		a += str(count % 2)
	else:
		a += str(count % 2)
		count += 1
print(a)


n = int(input())
s = input()
count = 0
ans = ''
for i in range(n):
	if s[i] == '(':
		if count % 2 == 0:
			ans += '0'
		else:
			ans += '1'
		count += 1
	else:
		count -= 1
		if count % 2 == 0:
			ans += '0'
		else:
			ans += '1'
print(ans)


n = int(input())
string = [str(x) for x in str(input())]
r_score = 0
b_score = 0
answer = ''
for char in range(n):
	cur_char = string[char]
	if cur_char == '(':
		if r_score > b_score:
			b_score += 1
			answer = answer + '1'
		else:
			r_score += 1
			answer = answer + '0'
	elif r_score > b_score:
		r_score -= 1
		answer = answer + '0'
	else:
		b_score -= 1
		answer = answer + '1'
print(answer)


import math
import re
import sys
from collections import defaultdict
from heapq import heappush, heappop
from fractions import gcd

def read(type=int):
	return type(input())

def read_list(type=int, split=' '):
	return list(map(type, input().split(split)))

def read_list_of_list(N, type=int, split=' '):
	return [read_list(type) for _ in range(N)]
n = read()
s = read(str)
color = 0
X = ''
for c in s:
	if c == '(':
		X += str(color)
		color = 1 - color
	else:
		color = 1 - color
		X += str(color)
print(X)


n = int(input())
s = input()
d = 0
res = [0] * n
for (i, c) in enumerate(s):
	if c == '(':
		d += 1
		res[i] = d & 1
	else:
		res[i] = d & 1
		d -= 1
print(''.join(map(str, res)))


n = int(input())
s = input()
stack = []
a = [1] * n
d = {1: '0', 0: '1'}
out = ['1'] * n
for i in range(n):
	if stack and stack[-1][0] == '(':
		if s[i] == ')':
			a[i] = a[i - 1]
		else:
			a[i] = a[i - 1] + 1
		stack.append([s[i], a[i]])
	else:
		if s[i] == ')':
			a[i] = a[i - 1] - 1
		else:
			a[i] = a[i - 1]
		stack.append([s[i], a[i]])
	out[i] = d[a[i] % 2]
print(''.join(out))


input()
depth = [0, 0]
colors = []
seq = input()
for c in seq:
	if c == '(':
		if depth[0] < depth[1]:
			colors.append(0)
			depth[0] += 1
		else:
			colors.append(1)
			depth[1] += 1
	elif depth[0] > depth[1]:
		colors.append(0)
		depth[0] -= 1
	else:
		colors.append(1)
		depth[1] -= 1
print(*colors, sep='')


n = int(input())
queue = []
s = input()
turn = 0
top = 0
ans = []
for i in range(n):
	if s[i] == '(':
		ans.append(turn)
		queue.append(turn)
		turn ^= 1
	else:
		ans.append(queue[top])
		top += 1
print(''.join((str(x) for x in ans)))


def read_few_numbers():
	nums = map(int, input().split(' '))
	return nums
n = int(input())
s = input()
output = ''
blue_level = 0
red_level = 0
blue_string = ''
red_string = ''
for i in range(n):
	if s[i] == '(':
		if blue_level < red_level:
			output += '0'
			blue_level += 1
			blue_string += '('
		else:
			red_level += 1
			red_string += '('
			output += '1'
	elif s[i] == ')':
		if blue_level > red_level:
			output += '0'
			blue_level -= 1
			blue_string += ')'
		else:
			output += '1'
			red_string += ')'
			red_level -= 1
print(output)


from sys import stdin, stdout
N = int(input())
s = input()
L1 = 0
L2 = 0
ans = [0] * N
for i in range(N):
	if s[i] == '(':
		if L1 <= L2:
			L1 += 1
			ans[i] = 0
		else:
			L2 += 1
			ans[i] = 1
	if s[i] == ')':
		if L1 <= L2:
			L2 -= 1
			ans[i] = 1
		else:
			L1 -= 1
			ans[i] = 0
print(*ans, sep='')


def solve(s):
	nest = nesting(s)
	sorted_nest = sorted(enumerate(nest), key=lambda x: x[1], reverse=True)
	indexes = []
	min_nest_b = sorted_nest[0][1] // 2
	for x in sorted_nest:
		if x[1] > min_nest_b:
			indexes.append(x[0])
	return indexes

def nesting(s):
	current_nest = 0
	ans = []
	for bracket in s:
		if bracket == '(':
			current_nest += 1
		ans.append(current_nest)
		if bracket == ')':
			current_nest -= 1
	return ans

def format_ans(indexes, s):
	ans = []
	indexes = set(indexes)
	for i in range(len(s)):
		if i in indexes:
			ans.append('0')
		else:
			ans.append('1')
	return ''.join(ans)
input()
s = input()
indexes = solve(s)
print(format_ans(indexes, s))


from sys import *
N = int(input())
stack = []
signs = []
S = stdin.readline()
ans = ''
for s in range(N):
	if stack == [] or S[s] == '(':
		stack.append(S[s])
		if signs == []:
			signs.append(0)
		else:
			signs.append(signs[-1] ^ 1)
		ans += str(signs[-1])
	else:
		stack.pop()
		ans += str(signs[-1])
		signs.pop()
print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
s = input()
r = 0
b = 0
rb = []
for i in range(n):
	if s[i] == '(':
		if r < b:
			r += 1
			rb.append(0)
		else:
			b += 1
			rb.append(1)
	elif r > b:
		r -= 1
		rb.append(0)
	else:
		b -= 1
		rb.append(1)
print(*rb, sep='')


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import *
from operator import itemgetter, attrgetter
from decimal import *
import bisect
import math
import heapq as hq
MOD = 10 ** 9 + 7

def is_prime(n):
	if n == 2 or n == 3:
		return True
	if n < 2 or n % 2 == 0:
		return False
	if n < 9:
		return True
	if n % 3 == 0:
		return False
	r = int(n ** 0.5)
	f = 5
	while f <= r:
		if n % f == 0:
			return False
		if n % (f + 2) == 0:
			return False
		f += 6
	return True

def pow(a, b, m):
	ans = 1
	while b:
		if b & 1:
			ans = ans * a % m
		b //= 2
		a = a * a % m
	return ans
vis = []
graph = []

def dfs(v):
	if vis[v]:
		return 0
	vis[v] = True
	temp = 0
	for vv in graph[v]:
		temp += dfs(vv)
	return 1 + temp

def ispalindrome(s):
	if s[:] == s[::-1]:
		return 1
	return 0
ans = ''
n = int(input())
s = input()
open = ['0' for i in range(n)]
bal = 0
for i in range(n):
	if s[i] == ')':
		bal -= 1
	open[i] = str(bal % 2)
	if s[i] == '(':
		bal += 1
temp = ''
print(''.join(open))


input()
D = [0, 0]
maxd = 0
for c in input():
	if c == '(':
		(_, i) = min(((D[i], i) for i in range(2)))
		print(i, end='')
		D[i] += 1
		maxd = max(maxd, D[i])
	else:
		(_, i) = max(((D[i], i) for i in range(2)))
		print(i, end='')
		D[i] -= 1
print()


n = int(input())
s = input()
r = 0
b = 0
ans = []
for i in s:
	if i == '(':
		if r < b:
			ans.append(1)
			b -= 1
		else:
			ans.append(0)
			r -= 1
	elif r > b:
		ans.append(1)
		b += 1
	else:
		ans.append(0)
		r += 1
for i in ans:
	print(i, end='')


n = int(input())
s = input()
r = []
x = True
for v in s:
	if v == '(':
		r.append('0' if x else '1')
		x = not x
	elif v == ')':
		x = not x
		r.append('0' if x else '1')
print(''.join(r))


n = int(input())
paranthesis = input()
red_open = 0
blue_open = 0
depth_red = 0
depth_blue = 0
stack = []
colours = []
for x in range(0, len(paranthesis)):
	if paranthesis[x] == '(':
		stack.append('(')
		if red_open > blue_open:
			blue_open = blue_open + 1
			if blue_open > depth_blue:
				depth_blue = blue_open
			colours.append(1)
		elif red_open < blue_open:
			red_open = red_open + 1
			if red_open > depth_red:
				depth_red = red_open
			colours.append(0)
		elif depth_red > depth_blue:
			blue_open = blue_open + 1
			if blue_open > depth_blue:
				depth_blue = blue_open
			colours.append(1)
		else:
			red_open = red_open + 1
			if red_open > depth_red:
				depth_red = red_open
			colours.append(0)
	else:
		stack.pop()
		if red_open > blue_open:
			red_open = red_open - 1
			colours.append(0)
		elif blue_open > red_open:
			blue_open = blue_open - 1
			colours.append(1)
		elif depth_red > depth_blue:
			red_open = red_open - 1
			colours.append(0)
		else:
			blue_open = blue_open - 1
			colours.append(1)
for i in colours:
	print(i, end='')


N = int(input())
S = input()
T = [0] * N
L = 0
for (i, s) in enumerate(S):
	if s == '(':
		L += 1
		T[i] = L
	else:
		T[i] = L
		L -= 1
print(''.join(['0' if t % 2 else '1' for t in T]))


n = int(input())
s = input()
(c, cur) = (0, 0)
ans = [0] * n
for i in range(n):
	if s[i] == '(':
		ans[i] = c
		c = (c + 1) % 2
	else:
		ans[i] = cur
		cur = (cur + 1) % 2
print(*ans, sep='')


n = int(input())
s = str(input())
l = [1]
contr = 1
for i in range(1, n):
	if s[i] == '(' and s[i - 1] == '(':
		contr += 1
	if s[i] == ')' and s[i - 1] == ')':
		contr -= 1
	l.append(contr)
m = max(l)
c = m // 2 + 1
b = set()
ind = set()
i = 0
while i < n:
	if l[i] >= c and l[i] <= m:
		ind.add(i)
	i += 1
b = []
for i in range(n):
	if i in ind:
		b.append(1)
	else:
		b.append(0)
print(''.join([str(i) for i in b]))


n = int(input())
s = input()
a = []
ans = []
start = 0
count = 0
for i in range(n):
	if s[i] == '(':
		if count == 0:
			a.append(1)
			ans.append(1)
			count = 1
		else:
			a.append(0)
			ans.append(0)
			count = 0
	else:
		ans.append(a[start])
		start += 1
for c in ans:
	print(c, end='')
print()


n = int(input())
a = input()
b = []
c = 0
d = 0
for i in range(n):
	if a[i] == '(':
		c = c + 1
		b.append(c)
	elif a[i] == ')':
		d = d + 1
		b.append(d)
	b[i] = b[i] % 2
for i in range(n):
	print(b[i], end='')


n = int(input())
s = input()
a = [0] * n
cr = 0
cb = 0
for i in range(n):
	if s[i] == '(':
		if cr <= cb:
			a[i] = 0
			cr += 1
		else:
			a[i] = 1
			cb += 1
	elif cr >= cb:
		a[i] = 0
		cr -= 1
	else:
		a[i] = 1
		cb -= 1
print(''.join(map(str, a)))


n = int(input())
ss = list(input())
r = 0
b = 0
res = []
for s in ss:
	if s == '(':
		if r > b:
			res.append('0')
			b += 1
		else:
			res.append('1')
			r += 1
	elif r > b:
		res.append('1')
		r -= 1
	else:
		res.append('0')
		b -= 1
print(''.join(res))


n = int(input())
s = str(input())
p = []
c = 0
for i in s:
	if i == '(':
		p.append(c % 2)
		c += 1
	else:
		c -= 1
		p.append(c % 2)
print(''.join([str(i) for i in p]))


n = int(input())
s = input()
depth = 0
max1 = 0
loc = [0 for i in range(n)]
for i in range(n):
	if s[i] == '(':
		depth += 1
		loc[i] = depth
	else:
		loc[i] = depth
		depth -= 1
	max1 = max(max1, depth)
bre = max1 // 2
ans = ''
for i in range(n):
	if loc[i] <= max1 // 2:
		ans += '0'
	else:
		ans += '1'
print(ans)


a = int(input())
red = 0
blue = 0
li = []
if a == 2:
	input()
	print(11)
else:
	Evenprnths = input()
	for elem in Evenprnths:
		if elem == '(':
			if red > blue:
				blue += 1
				print(0, end='')
			else:
				red += 1
				print(1, end='')
		elif elem == ')':
			if blue > red:
				blue -= 1
				print(0, end='')
			else:
				red -= 1
				print(1, end='')
print()


from collections import deque
n = int(input())
s = input()

def find_max_nesting(s):
	stack = deque()
	curr = 0
	res = []
	for el in s:
		if el == '(':
			stack.append(curr)
			res.append(curr)
			curr = 1 if not curr else 0
		else:
			top_el = stack.pop()
			res.append(top_el)
			curr = 1 if stack and (not stack[-1]) else 0
	return res
res = find_max_nesting(s)
print(''.join(map(str, res)))


n = input()
s = input()
cur_depth = 0
max_depth = 0
depth_map = []
for si in s:
	if si == '(':
		cur_depth += 1
		max_depth = cur_depth if cur_depth > max_depth else max_depth
		depth_map.append(cur_depth)
	else:
		depth_map.append(cur_depth)
		cur_depth -= 1
half_depth = int(max_depth / 2)
for depth in depth_map:
	print(0 if depth <= half_depth else 1, end='')
print('\n')


n = int(input())
s = str(input())
t = ''
balance = 0
for i in range(n):
	if s[i] == ')':
		balance -= 1
	if balance & 1 == 1:
		t = t + '1'
	else:
		t = t + '0'
	if s[i] == '(':
		balance += 1
print(t)


from collections import *
from math import *
n = int(input())
s = list(input())
st = 0
ct = [0, 0]
l = []
for i in s:
	if i == ')':
		if ct[0] > ct[1]:
			ct[0] -= 1
			l.append(0)
		else:
			ct[1] -= 1
			l.append(1)
	elif ct[0] < ct[1]:
		ct[0] += 1
		l.append(0)
	else:
		ct[1] += 1
		l.append(1)
for i in l:
	print(i, end='')
print()


class Stack:

	def __init__(self, max_size):
		self.stack = [None for i in range(max_size)]
		self.size = 0

	def add(self, val):
		self.stack[self.size] = val
		self.size += 1

	def pop(self):
		val = self.stack[self.size - 1]
		self.size -= 1
		return val

	def empty(self):
		return len(self.stack) == 0

def conv(a):
	if a:
		return '1'
	else:
		return '0'

def solve(a):
	n = len(a)
	st = Stack(200005)
	ans = []
	cur = False
	for x in a:
		if x == '(':
			st.add(cur)
			ans.append(cur)
			cur = not cur
		else:
			val = st.pop()
			ans.append(val)
			cur = bool(val)
	return list(map(conv, ans))
a = input()
a = input()
print(''.join(solve(a)))