AtCoder Beginner Contest 064 - Insertion

You are given a string S of length N consisting of ( and ). Your task is to insert some number of ( and ) into S to obtain a correct bracket sequence.

Here, a correct bracket sequence is defined as follows:  
 - () is a correct bracket sequence.
 - If X is a correct bracket sequence, the concatenation of (, X and ) in this order is also a correct bracket sequence.
 - If X and Y are correct bracket sequences, the concatenation of X and Y in this order is also a correct bracket sequence.
 - Every correct bracket sequence can be derived from the rules above.
Find the shortest correct bracket sequence that can be obtained. If there is more than one such sequence, find the lexicographically smallest one.

-----Constraints-----
 - The length of S is N.
 - 1 ≤ N ≤ 100
 - S consists of ( and ).

-----Input-----
Input is given from Standard Input in the following format:
N
S

-----Output-----
Print the lexicographically smallest string among the shortest correct bracket sequences that can be obtained by inserting some number of ( and ) into S.

-----Sample Input-----
3
())

-----Sample Output-----
(())

Source: atcoder | Difficulty: MEDIUM


Solutions:
n = int(input())
s = input()
d = [0] * n
lcount = 0
rcount = 0
for i in range(len(s)):
	if s[i] == '(':
		lcount += 1
	elif lcount >= 1:
		lcount -= 1
	else:
		rcount += 1
print('(' * rcount + s + ')' * lcount)


N = int(input())
S = input()
s = S[:]
while '()' in s:
	s = s.replace('()', '')
ans = '(' * s.count(')') + S + ')' * s.count('(')
print(ans)


n = int(input())
s = input()
t = s
while '()' in s:
	s = s.replace('()', '')
print(s.count(')') * '(' + t + ')' * s.count('('))


n = int(input())
s = input()
counter_l = 0
pairs = 0
double_check = set()
for i in range(n):
	if s[i] == '(':
		counter_l += 1
		for j in range(i + 1, n):
			if s[j] == ')' and j not in double_check:
				pairs += 1
				double_check.add(j)
				break
counter_r = n - counter_l
s = s + ')' * (counter_l - pairs)
s = '(' * (counter_r - pairs) + s
print(s)


input()
s = input()
l = 0
exec("r=l\nfor c in'%s':l=max(l-1+2*(c=='%s'),0)\n" * 2 % (s, '(', s[::-1], ')'))
print(l * '(' + s + ')' * r)


n = int(input())
s = input()
d = [0]
cnt = 0
for i in range(n):
	if s[i] == '(':
		cnt += 1
	else:
		cnt -= 1
	d.append(cnt)
x = min(d)
print('(' * -x + s + ')' * (d[-1] - x))


N = int(input())
S = input()
l = ''
r = ''
cnt = 0
for i in S:
	if i == '(':
		cnt += 1
	else:
		cnt -= 1
	if cnt < 0:
		cnt += 1
		l += '('
r = ')' * cnt
print(l + S + r)


n = int(input())
s = input()
i = 0
k = 0
while i < len(s):
	if s[i] == '(':
		k += 1
	elif k > 0:
		k -= 1
	else:
		s = '(' + s
		i += 1
	i += 1
print(s + ')' * k)


from collections import deque
n = int(input())
s = deque(input())
left = 0
right = 0
for i in range(n):
	if s[i] == '(':
		left += 1
	elif left > 0:
		left -= 1
	else:
		right += 1
for _ in range(left):
	s.append(')')
for _ in range(right):
	s.appendleft('(')
print(''.join(s))


n = int(input())
s = input()
(a, b) = (0, 0)
for c in s:
	if c == ')':
		if a:
			a -= 1
		else:
			b += 1
	else:
		a += 1
print(b * '(' + s + a * ')')


n = input()
s = input()
x = s
while '()' in x:
	x = x.replace('()', '')
print('(' * x.count(')') + s + ')' * x.count('('))


n = int(input())
s = input()
t = s
while '()' in t:
	t = t.replace('()', '')
a = t.count(')')
b = t.count('(')
print('(' * a + s + ')' * b)


n = int(input())
s = list(input())
d = [0]
x = 0
for i in range(len(s)):
	if s[i] == '(':
		x += 1
	else:
		x -= 1
	d.append(x)
ans = []
x = min(d)
for i in range(max(0, -1 * x)):
	ans.append('(')
for i in s:
	ans.append(i)
for i in range(max(d[len(d) - 1] - x, 0)):
	ans.append(')')
a = ''.join(ans)
print(a)


n = int(input())
s = input()
cntr = 0
for i in range(n - 1, -1, -1):
	if s[i] == ')':
		cntr += 1
	elif cntr > 0:
		cntr -= 1
s = '(' * cntr + s
n = len(s)
cntl = 0
for i in range(n):
	if s[i] == '(':
		cntl += 1
	elif cntl > 0:
		cntl -= 1
s += ')' * cntl
print(s)


n = int(input())
s = input()
l = 0
r = 0
for i in s:
	if i == ')' and l == 0:
		r += 1
	elif i == ')':
		l -= 1
	elif i == '(':
		l += 1
s1 = '(' * r
s2 = ')' * l
s = s1 + s + s2
print(s)


n = int(input())
S = input()
T = S.replace('()', '')
for _ in range(50):
	T = T.replace('()', '')
print('(' * T.count(')') + S + ')' * T.count('('))


n = int(input())
s = input()
(l, r, c) = (0, 0, 0)
for a in s:
	if a == '(':
		c += 1
	elif c:
		c -= 1
	else:
		l += 1
r = c
print('(' * l + s + ')' * r)


from itertools import accumulate
N = int(input())
S = input()
m = -min(min(accumulate((1 if c == '(' else -1 for c in S))), 0)
s = sum((1 if c == '(' else -1 for c in S))
print('(' * m + S + ')' * (s + m))


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


N = int(input())
S = input()
s = S
for _ in range(50):
	s = s.replace('()', '')
ans = '(' * s.count(')') + S + ')' * s.count('(')
print(ans)


def main():
	N = int(input())
	S = input()
	solo_close_no = 0
	for i in range(N):
		if S[-i - 1] == ')':
			solo_close_no += 1
		elif solo_close_no >= 1:
			solo_close_no -= 1
	solo_open_no = 0
	for i in range(N):
		if S[i] == '(':
			solo_open_no += 1
		elif solo_open_no >= 1:
			solo_open_no -= 1
	answer = '(' * solo_close_no + S + ')' * solo_open_no
	print(answer)

def __starting_point():
	main()
__starting_point()


n = int(input())
s = input()
ans = s
let = 0
let2 = ''
for i in range(n):
	if s[i] == '(':
		let += 1
	elif let > 0:
		let -= 1
	else:
		let2 += '('
print(let2 + s + ')' * let)


import copy
N = int(input())
S = list(input())
S_ans = copy.deepcopy(S)
app = 0
q = [0]
save = 0
for i in range(N):
	if S[i] == '(':
		q.append(q[-1] + 1)
	else:
		q.append(q[-1] - 1)
		if q[-1] == -1:
			S_ans.insert(app + save, '(')
			app += 1
			q[-1] = 0
for i in range(q[-1]):
	S_ans.append(')')
print(''.join(S_ans))


N = int(input())
S = input()
i = 0
c = 0
min_c = 0
while i < N:
	if S[i] == '(':
		c += 1
	else:
		c -= 1
	min_c = min(c, min_c)
	i += 1
print('(' * -min_c + S + ')' * (c - min_c))


n = int(input())
s = input()
a = s
f = 0
for c in a:
	if c == '(':
		f += 1
	elif f > 0:
		f -= 1
	else:
		s = '(' + s
for i in range(f):
	s = s + ')'
print(s)


n = int(input())
N = input()
L = 0
R = 0
num = 0
for c in N:
	if c == '(':
		num += 1
	elif num:
		num -= 1
	else:
		L += 1
R = num
print('(' * L + N + ')' * R)


N = int(input())
S = input()
mi = 0
ma = 0
c = 0
for it in S:
	if it == '(':
		c += 1
	else:
		c -= 1
	mi = min(c, mi)
	ma = max(c, ma)
print('(' * max(-mi, 0) + S + ')' * max(c - mi, 0))


N = int(input())
S = input()
now = 0
right = 0
left = 0
add_left = 0
while now < N:
	if S[now] == '(':
		left += 1
	elif left:
		left -= 1
	else:
		add_left += 1
	now += 1
for _ in range(add_left):
	print('(', end='')
print(S, end='')
for _ in range(left):
	print(')', end='')


def main():
	N = int(input())
	S = input()
	brackets = [0, 0]
	for i in range(len(S)):
		if S[i] == ')':
			if brackets[0] > 0:
				brackets[0] -= 1
			else:
				brackets[1] += 1
		elif S[i] == '(':
			brackets[0] += 1
	print(brackets[1] * '(' + S + brackets[0] * ')')
main()


N = int(input())
S = input()
cnt = 0
L = 0
for x in S:
	if x == '(':
		cnt += 1
	elif cnt > 0:
		cnt -= 1
	else:
		L += 1
print('(' * L + S + ')' * cnt)


n = int(input())
s = input()
l = 0
ans = ''
for e in s:
	if e == ')':
		if l <= 0:
			ans += '('
		else:
			l -= 1
	else:
		l += 1
print(ans + s + ')' * l)


n = int(input())
s = input()
r = 0
l = 0
cnt = 0
for i in s:
	if i == ')':
		cnt += 1
		if cnt > 0:
			cnt -= 1
			l += 1
	else:
		cnt -= 1
print(l * '(' + s + ')' * -cnt)


n = int(input())
s = input()
L = 0
R = 0
for i in s:
	if i == ')':
		if R:
			R -= 1
		else:
			L += 1
	else:
		R += 1
print('(' * L + s + ')' * R)


n = int(input())
s = input()
l = []
for i in s:
	if i == ')':
		if len(l) > 0:
			if l[-1] == '(':
				l.pop()
			else:
				l.append(i)
		else:
			l.append(i)
	else:
		l.append(i)
print(l.count(')') * '(' + s + l.count('(') * ')')


input()
t = s = input()
(p, q) = o = '()'
while o in s:
	s = s.replace(o, '')
print(p * s.count(q) + t + q * s.count(p))


N = int(input())
S = input()
T = [+1 if s == '(' else -1 for s in S]
from itertools import accumulate
Tcumsum = list(accumulate(T))
i = max(0, -min(Tcumsum))
print('(' * i + S + ')' * (Tcumsum[-1] + i))


input()
s = t = input()
(l, r) = p = '()'
exec("t=t.replace('()','');" * 50)
c = t.count
print(l * c(r) + s + r * c(l))


(l, r) = (0, 0)
N = int(input())
S = input()
for s in S:
	if s == '(':
		r += 1
	elif s == ')':
		if r > 0:
			r -= 1
		else:
			l += 1
print('(' * l + S + ')' * r)


n = input()
s = input()
ss = s
for i in range(50):
	s = s.replace('()', '')
l = s.count(')')
r = s.count('(')
print('(' * l + ss + ')' * r)


n = int(input())
s = input()
a = 0
b = 0
for i in s:
	if i == '(':
		a += 1
	elif a > 0:
		a -= 1
	else:
		b += 1
print('(' * b + s + ')' * a)


n = int(input())
s = input()
mn = 0
sm = 0
for i in range(n):
	sm += 1 if s[i] == '(' else -1
	mn = min(mn, sm)
mn *= -1
print('(' * mn + s + ')' * (sm + mn))


n = int(input())
s = input()
cnt = 0
for i in s:
	if i == '(':
		cnt += 1
	elif cnt >= 1:
		cnt -= 1
cnt2 = 0
for i in range(n - 1, -1, -1):
	if s[i] == ')':
		cnt2 += 1
	elif cnt2 >= 1:
		cnt2 -= 1
print('(' * cnt2 + s + ')' * cnt)


(_, S, l, r) = (input(), input(), '(', ')')
t = S
while t.count(l + r):
	t = t.replace(l + r, '')
print(l * t.count(r) + S + r * t.count(l))


N = int(input())
S = input()
flg_l = False
cnt_r = 0
cnt_l = 0
for i in range(N):
	if S[i] == '(':
		cnt_r += 1
		flg_l = True
	elif flg_l:
		if cnt_r > 0:
			cnt_r -= 1
		else:
			cnt_l += 1
			flg_l = False
	else:
		cnt_l += 1
ans = ''
ans += '(' * cnt_l + S + ')' * cnt_r
print(ans)


N = int(input())
S = input()
state = [0]
for s in S:
	state.append(state[-1] + (1 if s == '(' else -1))
ans = -min(state) * '(' + S + (state[-1] - min(state)) * ')'
print(ans)


n = int(input())
s = input()
(R, L) = (0, 0)
for i in range(len(s)):
	if s[i] == '(':
		R += 1
	elif R:
		R -= 1
	else:
		L += 1
print('(' * L + s + ')' * R)


N = int(input())
S = str(input())
s = S[:]
while '()' in s:
	s = s.replace('()', '')
st = s.count(')')
gl = s.count('(')
print('(' * st + S + ')' * gl)


N = int(input())
S = input()
cr = 0
cl = 0
for i in range(N):
	if S[i] == '(':
		cr += 1
	elif cr > 0:
		cr -= 1
	else:
		cl += 1
print('(' * cl + S + ')' * cr)


n = int(input())
a = input()
s = list(a)
from copy import copy
ans = copy(s)
left = 0
right = 0
for i in range(n):
	if s[i] == '(':
		left += 1
	elif left == 0:
		right += 1
	else:
		left -= 1
print('(' * right + str(a) + ')' * left)


N = int(input())
S = input()
x = 0
m = 0
for i in range(N):
	if S[i] == '(':
		x += 1
	else:
		x -= 1
		m = min(x, m)
a = -m
b = x - m
print('(' * a + S + ')' * b)


N = int(input())
X = input()
(L, R) = (0, 0)
for x in X:
	if x == '(':
		R += 1
	elif R == 0:
		L += 1
	else:
		R -= 1
print(L * '(' + X + R * ')')


n = int(input())
s = input()
a = 0
b = 0
p = 0
for i in range(len(s)):
	if s[i] == '(':
		a += 1
	if s[i] == ')':
		b += 1
		a -= 1
		if a < 0:
			p += 1
			a = 0
print('(' * p + s + ')' * a)


n = int(input())
s = input()
ans = s
while s.count('()') > 0:
	s = s.replace('()', '')
cnt_l = s.count(')')
cnt_r = s.count('(')
print(cnt_l * '(' + ans + cnt_r * ')')


from collections import deque
n = int(input())
s = input()
q = deque([])
t = ''
for i in s:
	if i == '(':
		q.append(i)
	elif q:
		q.pop()
	else:
		t += '('
u = ')' * len(q)
print(t + s + u)


from collections import deque
N = int(input())
S = input()
reserveL = deque()
out = deque()
q = deque()
for s in S:
	if s == '(':
		reserveL.append(s)
		out.append('(')
	elif len(reserveL) == 0:
		out.appendleft('(')
		out.append(')')
	else:
		out.append(')')
		reserveL.popleft()
while reserveL:
	out.append(')')
	reserveL.popleft()
ans = ''
while out:
	ans += out.popleft()
print(ans)


n = int(input())
s = input()
a = []
for i in s:
	if a and a[-1] == '(' and (i == ')'):
		a.pop()
	else:
		a.append(i)
c = a.count('(')
d = a.count(')')
print('(' * d + s + ')' * c)


input()
s = t = input()
(p, q) = o = '()'
exec('s=s.replace(o,"");' * 50)
f = s.count
print(p * f(q) + t + q * f(p))


N = int(input())
S = input()
prel = 0
prer = 0
for s in S:
	if s == '(':
		prel += 1
	if s == ')':
		if prel > 0:
			prel -= 1
		else:
			prer += 1
print(prer * '(' + S + prel * ')')


input()
s = input()
while 1:
	for i in range(len(s)):
		if s[i] == '(' and s[i:].count(')') < (len(s) - i) / 2:
			s += ')'
			break
	else:
		break
print('(' * (s.count(')') - s.count('(')) + s)


N = input()
S = input()
s = S
for i in range(50):
	S = S.replace('()', '')
l = S.count(')')
r = S.count('(')
print('(' * l + s + ')' * r)


N = int(input())
S = input()
t = S
while '()' in t:
	t = t.replace('()', '')
print('(' * t.count(')') + S + ')' * t.count('('))


def main():
	N = int(input())
	S = input()
	count = 0
	for i in range(N - 1, -1, -1):
		if S[i] == ')':
			count += 1
		elif count:
			count -= 1
		else:
			S += ')'
	S = '(' * count + S
	print(S)

def __starting_point():
	main()
__starting_point()


N = int(input())
S = input()
T = S
while S.count('()'):
	S = S.replace('()', '')
print(S.count(')') * '(' + T + S.count('(') * ')')


n = int(input())
s = input()
cnt = 0
M = 0
for i in s:
	if i == ')':
		cnt += 1
	else:
		cnt -= 1
	M = max(M, cnt)
print('(' * M + s + ')' * (M - cnt))


N = int(input())
S = input()
b = 0
e = 0
for s in S:
	if s == ')':
		e += 1
	else:
		b += 1
	S = '(' * max(e - b, 0) + S
	b += max(e - b, 0)
S += ')' * max(b - e, 0)
print(S)


n = int(input())
s = list(input())
c0 = 0
c1 = 0
z0 = 0
z1 = 0
for i in range(n):
	if s[i] == '(':
		c0 += 1
	elif c0 > 0:
		c0 -= 1
	else:
		c1 += 1
ans = ['('] * c1 + s + [')'] * c0
print(''.join(ans))


N = int(input())
S = input()
A = 0
B = 0
for s in S:
	if s == '(':
		A += 1
	elif s == ')' and A > 0:
		A -= 1
	else:
		B += 1
print('(' * B + S + ')' * A)


n = int(input())
s = input()
left = 0
right = 0
for i in range(n):
	if s[i] == '(':
		right += 1
	elif right > 0:
		right -= 1
	else:
		left += 1
print(left * '(' + s + right * ')')


N = int(input())
S = input()
oS = S
S = list(S)
cnt = 0
while True:
	p_cnt = cnt
	for i in range(len(S) - 1):
		if S[i] == '(' and S[i + 1] == ')':
			S.pop(i + 1)
			S.pop(i)
			cnt += 1
			break
	if cnt == p_cnt:
		break
cnt_open = 0
cnt_close = 0
for s in S:
	if s == '(':
		cnt_open += 1
	else:
		cnt_close += 1
ans = '(' * cnt_close + oS + ')' * cnt_open
print(ans)


import sys
input = sys.stdin.readline

def main():
	N = int(input())
	S = input().rstrip()
	ans = ''
	n_left = 0
	n_right = 0
	for s in S:
		if s == '(':
			n_left += 1
		elif n_left > 0:
			n_left -= 1
		else:
			n_right += 1
	ans = ''.join(('(' * n_right, S, ')' * n_left))
	print(ans)

def __starting_point():
	main()
__starting_point()


n = int(input())
s = input()
(l, r) = (0, 0)
for i in range(n):
	if s[i] == '(':
		r += 1
	elif r:
		r -= 1
	else:
		l += 1
ans = '(' * l + s + ')' * r
print(ans)


N = int(input())
S = input()
x = 0
d = 0
for i in range(N):
	if S[i:i + 1] == '(':
		d += 1
	elif S[i:i + 1] == ')':
		d -= 1
	x = min(x, d)
print('(' * -x + S + ')' * (d - x))


N = int(input())
S = input()
a = 0
b = 0
cnt = 0
for i in range(N):
	if S[i] == ')':
		b += 1
	else:
		a += 1
	cnt = max(cnt, b - a)
A = '(' * cnt + S
d = A.count(')')
e = A.count('(')
f = e - d
print(A + ')' * f)


n = int(input())
s = input()
st = 0
m = 0
lv = 0
for x in s:
	if x == '(':
		lv += 1
	else:
		lv -= 1
	m = min(m, lv)
gl = lv - m
st -= m
print('(' * st + s + ')' * gl)


n = int(input())
s = input()
x = 0
xmin = 0
for c in s:
	if c == '(':
		x += 1
	else:
		x -= 1
		xmin = min(xmin, x)
print('(' * -xmin + s + ')' * (x - xmin))


N = int(input())
S = input()
(x, y, z) = (0, 0, 0)
for i in range(N):
	if S[i] == '(':
		x += 1
	else:
		y += 1
	z = min(z, x - y)
print('(' * -z + S + ')' * max(0, x - z - y))


n = int(input())
S = input()
(L, R) = (0, 0)
(l, r) = (0, 0)
for i in S:
	if i == '(':
		l += 1
	else:
		l -= 1
		L = min(L, l)
for i in S[::-1]:
	if i == ')':
		r += 1
	else:
		r -= 1
		R = min(R, r)
print('(' * -L + S + ')' * -R)


input()
s = input()
kakko = ''
num = 0
for c in s:
	if c == '(':
		num += 1
	elif num == 0:
		kakko += '('
	else:
		num -= 1
print(kakko + s + ')' * num)


N = int(input())
n = input()
l = 0
r = 0
for i in n:
	if i == '(':
		r += 1
	elif r:
		r -= 1
	else:
		l += 1
print('(' * l + n + ')' * r)


n = int(input())
S = input()
lc = 0
rc = 0
for s in S:
	if s == '(':
		rc += 1
	elif rc:
		rc -= 1
	else:
		lc += 1
print('(' * lc + S + ')' * rc)


N = int(input())
S = input()
nS = S
for i in range(50):
	nS = nS.replace('()', '')
r = nS.count(')')
l = nS.count('(')
print('(' * r + S + ')' * l)


n = int(input())
S = input()
l = 0
r = 0
for s in S:
	if s == '(':
		r += 1
	elif r > 0:
		r -= 1
	else:
		l += 1
ans = '(' * l + S + ')' * r
print(ans)


N = int(input())
S = input()
m = 0
min_m = 0
for c in S:
	if c == '(':
		m += 1
	else:
		m -= 1
	min_m = min(min_m, m)
ans = '(' * -min_m + S + ')' * (m - min_m)
print(ans)


n = int(input())
s = input()
c1 = 0
c2 = 0
c = 0
for i in s:
	if i == '(':
		c1 += 1
	else:
		c2 += 1
		if c1 + c < c2:
			c += 1
print('(' * c + s + ')' * (c + c1 - c2))


l = int(input())
m = input()
l = 0
r = 0
b = 0
for i in m:
	if i == ')':
		l += 1
	else:
		r += 1
	m = '(' * max(l - r, 0) + m
	r += max(l - r, 0)
m += ')' * max(r - l, 0)
print(m)


icase = 0
if icase == 0:
	n = int(input())
	s = input()
elif icase == 1:
	n = 3
	s = '())'
elif icase == 2:
	n = 6
	s = ')))())'
elif icase == 3:
	n = 8
	s = '))))(((('
l = []
r = []
sim = s[0]
if sim == '(':
	lidx = 0
	l.append(1)
	ridx = -1
elif sim == ')':
	lidx = 0
	l.append(0)
	ridx = 0
	r.append(1)
for i in range(1, len(s)):
	if s[i] == '(' and s[i - 1] == '(':
		l[lidx] += 1
	elif s[i] == '(' and s[i - 1] == ')':
		lidx += 1
		l.append(1)
	elif s[i] == ')' and s[i - 1] == ')':
		r[ridx] += 1
	elif s[i] == ')' and s[i - 1] == '(':
		ridx += 1
		r.append(1)
ll = sum(l)
rr = sum(r)
ds = ll - rr
if len(l) > len(r):
	r.append(0)
xmin = 0
x = 0
for i in range(len(l)):
	x = x + l[i] - r[i]
	xmin = min(x, xmin)
strs = '(' * -xmin + s + ')' * (ds - xmin)
print(strs)


_ = input()
S = input()
needs_right = 0
needs_left = 0
for c in S:
	if c == '(':
		needs_right += 1
	elif needs_right == 0:
		needs_left += 1
	else:
		needs_right -= 1
print('(' * needs_left + S + ')' * needs_right)


input()
s = input()
r = l = 0
for c in s:
	r = max(r - 1 + 2 * (c == '('), 0)
for c in s[::-1]:
	l = max(l - 1 + 2 * (c == ')'), 0)
print(l * '(' + s + ')' * r)


N = int(input())
S = input()
c = N
SS = S
while c > 0:
	SS = SS.replace('()', '')
	c = SS.count('()')
print('(' * SS.count(')') + S + ')' * SS.count('('))


N = int(input())
S = input()
T = S
while '()' in S:
	S = S.replace('()', '')
left = S.count(')')
right = S.count('(')
ans = '(' * left + T + ')' * right
print(ans)


(_, s) = (input(), input())
t = 0
for c in s:
	if c == '(':
		t += 1
	else:
		t -= 1
	if t < 0:
		s = '(' + s
		t += 1
print(s + ')' * t)


N = int(input())
S = input()
ans = S
count = 0
for i in range(N):
	if S[i] == '(':
		count += 1
	else:
		count -= 1
	if count < 0:
		ans = '(' + ans
		count += 1
count = 0
for i in range(N - 1, -1, -1):
	if S[i] == '(':
		count += 1
	else:
		count -= 1
	if count > 0:
		ans = ans + ')'
		count -= 1
print(ans)


from itertools import accumulate
N = int(input())
S = input()
SS = [1 if S[i] == '(' else -1 for i in range(N)]
SSS = list(accumulate(SS))
m = max(0, -min(SSS))
M = SSS[-1]
print('(' * m + S + ')' * (M + m))


n = int(input())
s = str(input())
l = []
(left, right) = (0, 0)
for c in s:
	if c == ')':
		if l == []:
			left += 1
		else:
			l.pop()
	else:
		l.append(1)
right = len(l)
print('(' * left + s + ')' * right)


N = int(input())
s = input()
org = s
while '()' in s:
	s = s.replace('()', '')
left = s.count(')')
right = s.count('(')
print('(' * left + org + ')' * right)


n = int(input())
s = input()
l = 0
r = 0
for i in range(n):
	if r == 0 and s[i] == ')':
		l += 1
	elif s[i] == '(':
		r += 1
	elif r > 0 and s[i] == ')':
		r -= 1
print('(' * l + s + ')' * r)


N = int(input())
S = input()
L = 0
R = 0
num = 0
for s in S:
	if s == '(':
		num += 1
	elif num:
		num -= 1
	else:
		L += 1
R = num
print('(' * L + S + ')' * R)


import sys
from collections import deque, defaultdict, namedtuple
import heapq
from math import sqrt, factorial, gcd, ceil, atan, pi

def input():
	return sys.stdin.readline()[:-1]
import string
import operator
import random
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
MOD = int(1000000000.0) + 7
INF = float('inf')
sys.setrecursionlimit(int(1000000.0))

def solve():
	n = int(input())
	s = input()
	stack = [-1]
	for e in s:
		if e == '(':
			stack.append(e)
		elif stack[-1] == '(':
			stack.pop()
		else:
			stack.append(e)
	l = stack.count(')')
	r = stack.count('(')
	print('(' * l + s + ')' * r)
T = 1
for case in range(1, T + 1):
	ans = solve()


N = int(input())
S = input()
cnt = 0
left = 0
for i in range(N):
	if S[i] == '(':
		cnt += 1
	elif cnt == 0:
		left += 1
	else:
		cnt -= 1
ans = '(' * left + S + ')' * cnt
print(ans)


N = int(input())
S = input()
d = [0]
o = c = 0
for i in range(N):
	if S[i] == '(':
		o += 1
	else:
		c += 1
	d.append(o - c)
x = min(d)
print('(' * -x + S + ')' * (d[-1] - x))


N = int(input())
S = input()
a = 0
b = 0
for i in S:
	if i == '(':
		a += 1
	elif a <= 0:
		b += 1
	else:
		a -= 1
print('(' * b + S + ')' * a)


input()
gt = input()
gtt = gt
for i in range(100):
	gt = gt.replace('()', '', 2)
num1 = gt.count('(')
num2 = gt.count(')')
print('(' * num2 + gtt + ')' * num1)


N = int(input())
S = input()
X = 0
front = 0
for s in S:
	X += s == '('
	X -= s == ')'
	if X < 0:
		X = 0
		front += 1
else:
	back = X
print('(' * front + S + ')' * back)


n = int(input())
s = input()
(op, cl) = (0, 0)
for c in s:
	if c == '(':
		op += 1
	elif op > 0:
		op -= 1
	else:
		cl += 1
print('(' * cl + s + ')' * op)


N = input()
s = input()
s1 = s
s2 = ''
while s1 != s2:
	s2 = s1
	s1 = s1.replace('()', '')
s2 = s1.replace('(', '')
print(len(s2) * '(' + s + (len(s1) - len(s2)) * ')')


n = int(input())
s = input()
c = [0]
for i in range(n):
	if s[i] == '(':
		c.append(c[-1] + 1)
	else:
		c.append(c[-1] - 1)
print(max(0, -min(c)) * '(' + s + max(0, c[-1] - min(c)) * ')')


n = int(input())
s = input()
b = l = r = 0
for i in s:
	if i == ')':
		l += 1
	if i == '(':
		r += 1
	if l > r:
		b += 1
		r += 1
print('(' * b + s + ')' * (r - l))


def main():
	import sys
	input = lambda : sys.stdin.readline().strip()
	N = int(input())
	S = input()
	right = 0
	left = 0
	for i in range(N):
		if S[i] == '(':
			right += 1
		elif right:
			right -= 1
		else:
			left += 1
	print(left * '(' + S + right * ')')

def __starting_point():
	main()
__starting_point()


with open(0) as f:
	(N, S) = f.read().split()
N = int(N)
S += '_'
left = 0
right = 0
cnt = 0
for i in range(N):
	cnt += {'(': 1, ')': -1}[S[i]]
	if S[i] == ')' and S[i + 1] != ')':
		if cnt < 0:
			left += -cnt
			cnt = 0
	if i == N - 1 and cnt > 0:
		right += cnt
ans = '(' * left + S[:N] + ')' * right
print(ans)


N = int(input())
S = input()
d = S
while d.count('()') != 0:
	d = d.replace('()', '')
l = d.count('(')
r = d.count(')')
z = '(' * r + S + ')' * l
print(z)


n = int(input())
s = input()
l = r = 0
ls = rs = 0
for i in s:
	if i == '(':
		l += 1
	else:
		r += 1
	if r > l:
		r -= 1
		ls += 1
print('(' * ls + s + (l - r) * ')')


n = int(input())
s = input()
l = 0
r = 0
for si in s:
	if si == '(':
		l += 1
	elif l == 0:
		r += 1
	else:
		l -= 1
print('(' * r + s + ')' * l)


N = int(input())
S = input()
l = r = 0
L = ''
for i in S:
	if i == '(':
		l += 1
	else:
		r += 1
	if l < r:
		L += '('
		l += 1
R = ')' * (l - r)
print(L + S + R)


n = int(input())
s = input()
c = 0
scount = 0
for (i, si) in enumerate(list(s)):
	if si == '(':
		c += 1
	else:
		c -= 1
	if c < 0:
		scount += 1
		c = 0
s = '(' * scount + s
s = s + ')' * c
print(s)


N = int(input())
S = input()
u = 0
l = 0
r = 0
for c in S:
	if c == '(':
		u += 1
	elif u:
		u -= 1
	else:
		l += 1
r = u
print('(' * l + S + ')' * r)


N = int(input())
S = input()
cnt1 = 0
cnt2 = 0
for i in range(N):
	if S[i] == '(':
		cnt1 += 1
	elif cnt1 > 0:
		cnt1 -= 1
	else:
		cnt2 += 1
print('(' * cnt2 + S + ')' * cnt1)


n = int(input())
S = input()
s = S[:]
while '()' in s:
	s = s.replace('()', '')
print('(' * s.count(')') + S + ')' * s.count('('))


N = int(input())
S = input()

def add1(S):
	cum = [0]
	for i in range(len(S)):
		if S[i] == '(':
			cum.append(cum[-1] + 1)
		else:
			cum.append(cum[-1] - 1)
	if min(cum) >= 0:
		return S
	out = '(' * -min(cum)
	out += S
	return out

def add2(S):
	cum = [0]
	for i in range(len(S)):
		if S[i] == '(':
			cum.append(cum[-1] + 1)
		else:
			cum.append(cum[-1] - 1)
	if cum[-1] == 0:
		return S
	n = cum[-1]
	out = S + ')' * n
	return out
S = add1(S)
S = add2(S)
print(S)


n = int(input())
s = list(input())
a = 0
b = 0
c = 0
for i in range(n):
	d = s[i]
	if d == '(':
		a += 1
	else:
		b += 1
		if b - c > a:
			c += 1
print('(' * c + ''.join(s) + ')' * (a - b + c))


import sys
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7

def resolve():
	n = int(input())
	S = input()
	right = 0
	left = 0
	for i in range(n):
		if S[i] == '(':
			left += 1
		elif left:
			left -= 1
		else:
			right += 1
	res = '(' * right + S + ')' * left
	print(res)

def __starting_point():
	resolve()
__starting_point()


input()
S = input()
c = 0
m = 0
for s in S:
	if s == '(':
		c += 1
	else:
		c -= 1
	if c < 0:
		m += 1
		c += 1
print('(' * m + S + ')' * c)


n = int(input())
s = str(input())
p = 0
q = 0
for i in range(n):
	if s[i] == ')':
		if q == 0:
			p += 1
		else:
			q -= 1
	else:
		q += 1
print('(' * p + s + ')' * q)


N = int(input())
s = input()
S = list(s)
left = 0
right = 0
for i in S:
	if i == '(':
		left += 1
	if i == ')':
		if left > 0:
			left -= 1
		else:
			right += 1
print('(' * right + s + ')' * left)


n = int(input())
s = input()
ss = s
while ss.count('()'):
	ss = ss.replace('()', '')
(left, right) = (ss.count('('), ss.count(')'))
print('(' * right + s + ')' * left)


n = int(input())
s = input()
ans = s
(l, r) = (0, 0)
for p in s:
	if p == '(':
		l += 1
	else:
		r += 1
	if r > l:
		ans = '(' + ans
		l += 1
print(ans + ')' * (l - r))


N = int(input())
S = input()
a = [0]
for c in S:
	a.append(a[-1] + (1 if c == '(' else -1))
k = -min(a)
l = S.count('(') + k - S.count(')')
ans = '(' * k + S + ')' * l
print(ans)


N = int(input())
S = input()
X = 0
ans = ''
for s in S:
	if s == '(':
		X += 1
	else:
		X -= 1
	if X < 0:
		ans += '('
		X = 0
ans += S + X * ')'
print(ans)


N = int(input())
S = input()
R = 0
L = 0
for i in range(N):
	if S[i] == ')':
		if L == 0:
			R += 1
		else:
			L -= 1
	else:
		L += 1
Answer = '(' * R + S + ')' * L
print(Answer)


n = int(input())
s = input()
(cnt_l, cnt_r) = (0, 0)
for x in s:
	if x == '(':
		cnt_l += 1
	elif cnt_l > 0:
		cnt_l -= 1
	else:
		cnt_r += 1
print(cnt_r * '(' + s + cnt_l * ')')


n = int(input())
s = input()
i = 0
mi = 0
for c in s:
	if c == '(':
		i += 1
	else:
		i -= 1
	mi = min(mi, i)
ans = '(' * -mi + s + ')' * (i - mi)
print(ans)


n = int(input())
s = input()
a = ''
stack = []
for i in range(len(s)):
	if s[i] == '(':
		stack.append('(')
		a += '('
	elif s[i] == ')' and len(stack) == 0:
		stack.append(')')
		a += ')'
	elif s[i] == ')' and stack[-1] == ')':
		stack.append(')')
		a += ')'
	else:
		stack.pop(-1)
		a += ')'
while len(stack) > 0:
	if stack[len(stack) - 1] == ')':
		e = len(stack) - 1
		s = e
		while s - 1 >= 0 and stack[s - 1] == ')':
			s -= 1
		a = '(' * (e - s + 1) + a
		stack = stack[:s]
	elif stack[len(stack) - 1] == '(':
		e = len(stack) - 1
		s = e
		while s - 1 >= 0 and stack[s - 1] == '(':
			s -= 1
		a = a + ')' * (e - s + 1)
		stack = stack[:s]
print(a)


n = int(input())
s = input()
X = [0]
r = 0
for i in range(n):
	if s[i] == '(':
		r += 1
	else:
		r -= 1
	X.append(r)
left = -min(X)
right = X[-1] + left
print('(' * left + s + ')' * right)


def main2():
	input()
	s = input()
	pair = [-1] * 2
	ans = s
	idx = 0
	for idx in range(0, len(s)):
		for i in range(idx, len(s)):
			if s[i] == '(':
				pair[0] = i if pair[0] == -1 else pair[0]
			elif s[i] == ')':
				pair[1] = i
				break
		if pair[0] != -1 and pair[1] != -1:
			s = s[:pair[0]] + ' ' + s[pair[0] + 1:pair[1]] + ' ' + s[pair[1] + 1:]
		elif pair[0] != -1 and pair[1] == -1:
			s = s[:pair[0]] + ' ' + s[pair[0] + 1:]
			ans = ans + ')'
		elif pair[0] == -1 and pair[1] != -1:
			s = s[:pair[1]] + ' ' + s[pair[1] + 1:]
			ans = '(' + ans
		pair = [-1] * 2
	print(ans)

def __starting_point():
	main2()
__starting_point()


n = int(input())
s = input()
l = 0
p = 0
for i in range(n):
	if s[i] == '(':
		l += 1
	elif l > 0:
		p += 1
		l -= 1
a = s.count('(')
b = s.count(')')
print('(' * (b - p) + s + ')' * (a - p))


N = int(input())
S = input()
T = list((1 if c == '(' else -1 for c in S))
(l, l_min) = (0, 0)
(r, r_min) = (0, 0)
for i in range(N):
	l += T[i]
	l_min = min(l_min, l)
	r -= T[N - i - 1]
	r_min = min(r_min, r)
print(''.join(['(' * -l_min, S, ')' * -r_min]))


N = int(input())
S = input()
i = 0
hidari = str()
migi = str()
a = 0
while i < N:
	if S[i] == ')':
		hidari += '('
		i += 1
	else:
		break
while i < N:
	if S[i] == '(':
		a += 1
	else:
		a -= 1
	i += 1
if a < 0:
	hidari += abs(a) * '('
elif a > 0:
	migi += a * ')'
s = hidari + S + migi
i = 0
hidari = str()
migi = str()
a = 0
while i < N:
	if S[i] == ')':
		hidari += '('
		i += 1
	else:
		break
while i < N:
	if S[i] == '(':
		if a < 0:
			a = 0
		a += 1
		mina = 0
	else:
		a -= 1
		if a < 0:
			if mina > a:
				hidari += '('
	i += 1
if a > 0:
	migi += a * ')'
t = hidari + S + migi
if len(s) == len(t):
	print(s)
elif len(s) > len(t):
	print(s)
else:
	print(t)


input()
S = input()
d = m = 0
for c in S:
	if c == '(':
		d -= 1
	else:
		d += 1
	m = max(d, m)
S = '(' * m + S
d = m = 0
for c in S[::-1]:
	if c == '(':
		d += 1
	else:
		d -= 1
	m = max(d, m)
print(S + ')' * m)


def main():
	n = int(input())
	s = input()
	(l, r, c) = (0, 0, 0)
	for a in s:
		if a == '(':
			c += 1
		elif c:
			c -= 1
		else:
			l += 1
	r = c
	print('(' * l + s + ')' * r)

def __starting_point():
	main()
__starting_point()


N = int(input())
S = list(input())
d = []
for i in range(N + 1):
	partial = S[:i]
	d.append(partial.count('(') - partial.count(')'))
a = -min(d)
b = d[-1]
print('(' * a + ''.join(S) + ')' * (b + a))


n = int(input())
s = input()
(cntl, cntr, tmp) = (0, 0, 0)
for i in range(n):
	if s[i] == ')':
		if cntl > 0:
			cntl -= 1
		else:
			cntr += 1
	else:
		cntl += 1
print(cntr * '(' + s + cntl * ')')


(n, s) = (int(input()), input())
(mx, lt, rt) = [0] * 3
for i in range(n):
	if s[i] == '(':
		lt += 1
	else:
		rt += 1
	mx = max(mx, rt - lt)
print('(' * mx + s + ')' * (lt + mx - rt))


(n, s) = open(0).read().split()
imp_close = 0
imp_open = 0
for char in s:
	if char == '(':
		imp_open += 1
	elif imp_open:
		imp_open -= 1
	else:
		imp_close += 1
print('(' * imp_close + s + ')' * imp_open)


N = int(input())
S = input()
dic = {'(': 1, ')': -1}
rlt = ''
cnt = 0
for s in S:
	cnt += dic[s]
	rlt += s
	if cnt < 0:
		rlt = '(' + rlt
		cnt = 0
if cnt > 0:
	rlt += ')' * cnt
print(rlt)


import sys
from collections import deque

def IN_I():
	return int(sys.stdin.readline().rstrip())

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

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

def IN_LS():
	return list(sys.stdin.readline().rstrip().split())
N = IN_I()
S = IN_S()
d = deque(S)
l = 0
for i in range(N):
	if S[i] == '(':
		l += 1
	elif l == 0:
		d.appendleft('(')
	else:
		l -= 1
r = 0
for i in range(N - 1, -1, -1):
	if S[i] == ')':
		r += 1
	elif r == 0:
		d.append(')')
	else:
		r -= 1
print(''.join(d))


n = int(input())
s = input()
while True:
	c = 0
	for i in range(len(s)):
		if s[i] == '(':
			c += 1
		else:
			c -= 1
		if c < 0:
			s = '(' + s
			break
	if c > 0:
		s = s + ')'
	if c == 0:
		print(s)
		break


N = int(input())
S = str(input())
(l, r) = (0, 0)
(p, m) = (0, 0)
for i in range(N):
	if S[i] == '(':
		l += 1
	else:
		r += 1
	if l < r:
		p += 1
		l += 1
m = l - r
for i in range(p):
	print('(', end='')
print(S, end='')
for i in range(m):
	print(')', end='')


N = int(input())
S = input()
left_cnt = 0
right_cnt = 0
for s in S:
	if s == '(':
		left_cnt += 1
	elif left_cnt == 0:
		right_cnt += 1
	else:
		left_cnt -= 1
S = '(' * right_cnt + S + ')' * left_cnt
print(S)


def main():
	import sys

	def input():
		return sys.stdin.readline().rstrip()
	n = int(input())
	s = input()
	cnt = 0
	m = 0
	for i in range(n):
		if s[i] == '(':
			cnt += 1
		else:
			cnt -= 1
		m = min(m, cnt)
	ans = '(' * -m + s + ')' * (cnt - m)
	print(ans)

def __starting_point():
	main()
__starting_point()


n = int(input())
s = input()
(l_num, r_num) = (0, 0)
for i in s:
	if i == '(':
		l_num += 1
	elif l_num <= 0:
		r_num += 1
	else:
		l_num -= 1
print('(' * r_num + s + ')' * l_num)


N = int(input())
S = input()
(b, k) = (0, 0)
for i in range(N):
	if S[i] == '(':
		b += 1
	else:
		k += 1
		if b > 0:
			k -= 1
			b -= 1
print('(' * k + S + ')' * b)


from math import gcd
from itertools import combinations, permutations, accumulate, product
from collections import deque, defaultdict, Counter
import decimal
import re
import math
import bisect
import heapq
import sys
sys.setrecursionlimit(10000000)
mod = 10 ** 9 + 7
INF = float('inf')
from sys import stdin
readline = stdin.readline

def readInts():
	return list(map(int, readline().split()))

def readTuples():
	return tuple(map(int, readline().split()))

def I():
	return int(readline())
n = I()
S = input()
left = 0
right = 0
for i in range(n):
	if S[i] == '(':
		right += 1
	elif S[i] == ')':
		if right >= 1:
			right -= 1
		else:
			left += 1
print('(' * left + S + ')' * right)


n = int(input())
s = input()
x = s
for i in range(50):
	x = x.replace('()', '')
l = x.count(')')
r = x.count('(')
for i in range(l):
	s = '(' + s
for i in range(r):
	s += ')'
print(s)


N = int(input())
S = input()
x = 0
y = 0
for i in S:
	if i == '(':
		x += 1
	elif x <= 0:
		y += 1
	else:
		x -= 1
print('(' * y + S + ')' * x)


N = int(input())
S = input()
add_left = 0
add_right = 0
for s in S:
	if s == '(':
		add_right += 1
	elif add_right == 0:
		add_left += 1
	else:
		add_right -= 1
print('(' * add_left + S + ')' * add_right)


input()
S = input()
left = right = 0
for c in S:
	if c == '(':
		left += 1
	elif left:
		left -= 1
	else:
		right += 1
print('(' * right + S + ')' * left)


n = int(input())
s = input()
l = ''
c = 0
d = 0
for i in range(n):
	if s[i] == '(':
		c += 1
	elif c > 0:
		c -= 1
	else:
		l += '('
print(l + s + ')' * c)


import copy
n = int(input())
s = input()
deeps = copy.deepcopy(s)
while s.count('()') >= 1:
	s = s.replace('()', '')
ans = s.count(')') * '(' + deeps + s.count('(') * ')'
print(ans)


n = int(input())
s = input()
d = [0] * (n + 1)
for i in range(1, n + 1):
	d[i] = s[:i].count('(') - s[:i].count(')')
x = min(d)
s = '(' * -x + s + ')' * (d[n] - x)
print(s)


n = int(input())
s = input()
a = [1 if i == '(' else -1 for i in s]
e = [0]
for i in range(n):
	e.append(e[i] + a[i])
s = -min(e) * '(' + s
s += (s.count('(') - s.count(')')) * ')'
print(s)


n = int(input())
s = input()
(cnt, L) = (0, 0)
for i in range(len(s)):
	if s[i] == '(':
		cnt += 1
	else:
		cnt -= 1
	if cnt < 0:
		L = min(L, cnt)
ans = '(' * abs(L) + s
R = ans.count('(') - ans.count(')')
ans += ')' * R
print(ans)


input()
t = s = input()
while '()' in s:
	s = s.replace('()', '')
print('(' * s.count(')') + t + ')' * s.count('('))


N = int(input())
S = input()
res = S
while '()' in res:
	res = res.replace('()', '')
ans = '(' * res.count(')') + S + ')' * res.count('(')
print(ans)


import re
N = int(input())
s = input()[:N]
s_check = s
s_check = re.sub('\\(\\)', '', s_check)
while len(s_check) > 0:
	for i in range(len(s_check)):
		if s_check[i] == ')':
			s = '(' + s
			s_check = '(' + s_check
			break
		elif s_check[i] == '(':
			break
	for i in range(len(s_check)):
		if s_check[-i - 1] == '(':
			s = s + ')'
			s_check = s_check + ')'
			break
		elif s_check[-i - 1] == ')':
			break
	s_check = re.sub('\\(\\)', '', s_check)
print(s)


n = int(input())
s = input()
s_ = s
while s_.count('()'):
	s_ = s_.replace('()', '')
l = s_.count(')')
r = len(s_) - l
ans = '(' * l + s + ')' * r
print(ans)


n = int(input())
s = input()
l = 0
r = 0
p = []
for i in range(n):
	if s[i] == '(':
		p.append('(')
	elif p == []:
		l += 1
	else:
		p.pop()
r = p.count('(')
print('(' * l + s + ')' * r)


n = int(input())
s = list(input())
s = s[::-1]
balance = 0
i = 0
while i < len(s):
	if s[i] == ')':
		balance += 1
	else:
		balance -= 1
	if balance < 0:
		s.insert(0, ')')
		balance += 1
		i += 1
	i += 1
balance = 0
i = 0
s = s[::-1]
while i < len(s):
	if s[i] == '(':
		balance += 1
	else:
		balance -= 1
	if balance < 0:
		s.insert(0, '(')
		balance += 1
		i += 1
	i += 1
print(''.join(s))


N = int(input())
S = input()
s = list(S)
cr = 0
cl = 0
for i in s:
	if i == '(':
		cr += 1
	elif cr > 0:
		cr -= 1
	else:
		cl += 1
print('(' * cl + S + ')' * cr)


n = int(input())
s = input()
l = 0
res = 0
for i in s:
	if i == '(':
		l += 1
	elif l:
		l -= 1
	else:
		res += 1
print(res * '(' + s + l * ')')


input()
S = input()
l = 0
r = 0
for s in S:
	if s == ')':
		if r:
			r -= 1
		else:
			l += 1
	else:
		r += 1
ans = '(' * l + S + ')' * r
print(ans)


from collections import deque
N = int(input())
S = input()
que = deque(S)
l = r = 0
for s in S:
	if s == '(':
		l += 1
	else:
		r += 1
	if l < r:
		que.appendleft('(')
		l += 1
else:
	ans = ''.join(que)
	if r < l:
		ans = ans + ')' * (l - r)
print(ans)


from math import ceil, floor, comb, factorial, gcd, pow, sqrt, log2, cos, sin, tan, acos, asin, atan, degrees, radians, pi, inf
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
from operator import itemgetter
from heapq import heapify, heappop, heappush
from queue import Queue, LifoQueue, PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)

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

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

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

def LIST():
	return list(MAP())
n = INT()
s = input()
count = 0
for i in range(n):
	if s[i] == '(':
		count += 1
	else:
		count = max(0, count - 1)
s += ')' * count
count = 0
for i in range(n - 1, -1, -1):
	if s[i] == ')':
		count += 1
	else:
		count = max(0, count - 1)
s = '(' * count + s
print(s)


N = int(input())
S = input()
nl = 0
nr = 0
for i in S:
	if i == ')':
		if nr > 0:
			nr -= 1
		else:
			nl += 1
	else:
		nr += 1
print('(' * nl + S + ')' * nr)


n = int(input())
s = input()
now = 0
sen = 0
for i in range(n):
	if s[i] == '(':
		now += 1
	else:
		now -= 1
	if now == -1:
		sen += 1
		now = 0
print('(' * sen + s + ')' * now)


import sys
input = sys.stdin.readline
from collections import deque

def read():
	N = int(input().strip())
	S = input().strip()
	return (N, S)

def solve(N, S):
	rank = 0
	q = deque()
	for s in S:
		if rank == 0:
			if s == ')':
				q.appendleft('(')
				q.append(')')
			else:
				q.append('(')
				rank += 1
		elif s == ')':
			q.append(')')
			rank -= 1
		else:
			q.append('(')
			rank += 1
	while rank > 0:
		q.append(')')
		rank -= 1
	return ''.join(q)

def __starting_point():
	inputs = read()
	print(solve(*inputs))
__starting_point()


N = int(input())
S = input()
output = ''
lr = 0
for s in S[::-1]:
	lr += 1 if s == ')' else -1
	if lr < 0:
		output += ')'
		lr = 0
	output = s + output
print('(' * lr + output)


n = int(input())
s = input()
(x, y, a) = (0, 0, 0)
for char in s:
	if char == '(':
		x += 1
	else:
		y += 1
	a = min(a, x - y)
	b = x - y
ans = '(' * -a + s + ')' * (b - a)
print(ans)


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


n = int(input())
s = input()
x = 0
y = 0
for i in range(n):
	if s[i] == '(':
		x += 1
	elif s[i] == ')':
		x -= 1
	if x < 0:
		y += 1
		x += 1
print('(' * y + s + ')' * x)


n = int(input())
s = input()
ans = []
minscore = 0
score = 0
for i in range(n):
	if s[i] == '(':
		score += 1
	else:
		score -= 1
	minscore = min(minscore, score)
finalscore = score
for i in range(-minscore):
	ans.append('(')
for i in range(n):
	ans.append(s[i])
for i in range(-minscore + finalscore):
	ans.append(')')
print(''.join(ans))


n = int(input())
s = input()
tmp = s
while '()' in tmp:
	tmp = tmp.replace('()', '')
left = tmp.count(')')
right = tmp.count('(')
ans = '(' * left + s + ')' * right
print(ans)


n = int(input())
s = input()
x = s
while 1:
	a = s.find('()')
	if a == -1:
		break
	s = s[:a] + s[a + 2:]
for i in range(len(s)):
	if s[i] == ')':
		x = '(' + x
	else:
		x = x + ')'
print(x)


N = int(input())
S = input()
T = S
for n in range(N):
	T = T.replace('()', '')
L = T.count('(')
R = T.count(')')
S = R * '(' + S + L * ')'
print(S)


N = int(input())
S = input()
stack = []
for c in S:
	if len(stack) > 0:
		last = stack[-1]
		if last == '(' and c == ')':
			stack = stack[:-1]
			continue
	stack.append(c)
left = stack.count(')')
right = stack.count('(')
print(left * '(' + S + right * ')')


n = int(input())
s = list(input())
ans = ''
l = 0
for i in range(n):
	ans += s[i]
	if s[i] == ')':
		if l == 0:
			ans = '(' + ans
		else:
			l -= 1
	else:
		l += 1
ans += ')' * l
print(ans)


N = int(input())
S = input()
l = 0
r = 0
for i in range(N):
	if S[i] == '(':
		l += 1
	elif l > 0:
		l -= 1
	else:
		r += 1
print('(' * r + S + ')' * l)


N = int(input())
S = input()
T = S
k = 0
for s in S:
	if s == '(':
		k += 1
	else:
		k -= 1
		if k == -1:
			T = '(' + T
			k = 0
print(T + ')' * k)


n = int(input())
s = str(input())
ns = s
while '()' in ns:
	ns = ns.replace('()', '')
l = ns.count(')')
r = ns.count('(')
print('(' * l + s + ')' * r)


N = int(input())
motoS = input()
S = list(motoS)
start = 0
end = 0
for i in range(N):
	if S[i] == '(':
		end += 1
	else:
		end -= 1
	if end < 0:
		start += 1
		end = 0
print('(' * start + motoS + ')' * end)


n = int(input())
s = input()
lp = 0
rp = 0
for i in range(n):
	if s[i] == '(':
		rp += 1
	else:
		rp = rp - min(rp, 1)
for i in range(n - 1, -1, -1):
	if s[i] == ')':
		lp += 1
	else:
		lp = lp - min(lp, 1)
print('(' * max(0, lp) + s + max(0, rp) * ')')


n = int(input())
s = input()
(countr, countl) = (0, 0)
for i in range(n - 1, -1, -1):
	if s[i] == ')':
		countr += 1
	elif countr > 0:
		countr -= 1
s = '(' * countr + s
n = len(s)
for i in range(n):
	if s[i] == '(':
		countl += 1
	elif countl > 0:
		countl -= 1
s += ')' * countl
print(s)


input()
s = input()
x = y = 0
for c in s:
	if c == '(':
		x += 1
	else:
		x -= 1
	y = max(y, -x)
print('(' * y + s + ')' * (x + y))


n = int(input())
s = input()
ss = s
for i in range(1 + n // 2):
	ss = ss.replace('()', '')
sta = ss.count('(')
end = ss.count(')')
print('(' * end + s + ')' * sta)


n = int(input())
s = input()
opens = 0
l = 0
for i in range(n):
	if s[i] == '(':
		opens += 1
	else:
		opens -= 1
		if opens < 0:
			l += 1
			opens = 0
print('(' * l + s + ')' * opens)


input()
S = input()
q = [-1]
for c in S:
	if c == ')' and q[-1] == 0:
		q.pop()
	elif c == ')':
		q.append(1)
	else:
		q.append(0)
print('(' * q.count(1) + S + ')' * q.count(0))


input()
s = input()
d = 0
x = 0
for c in s:
	if c == '(':
		d += 1
	else:
		d -= 1
	x = min(d, x)
print('(' * -x + s + ')' * (d - x))


N = int(input())
S = input()
d = [0] * (N + 1)
for i in range(N):
	d[i + 1] = d[i] + int(S[i] == '(') - int(S[i] == ')')
a = d[-1]
b = min(d)
print('(' * -b + S + ')' * (a - b))


input()
s = input()
c = 0
for i in s:
	if i == '(':
		c += 1
	elif c > 0:
		c -= 1
d = 0
for i in s[::-1]:
	if i == ')':
		d += 1
	elif d > 0:
		d -= 1
print('(' * d + s + ')' * c)


n = int(input())
s = input()
now = 0
rec = 0
for i in s:
	now += (-1) ** (i == ')')
	rec = min(now, rec)
(f, t) = ('', '')
if rec < 0:
	f = '(' * -rec
	now -= rec
if now > 0:
	t = ')' * now
print(f + s + t)


n = int(input())
s = input()
cnt1 = 0
cnt2 = 0
for i in range(n):
	if s[i] == '(':
		cnt1 += 1
	elif cnt1 > 0:
		cnt1 -= 1
	else:
		cnt2 += 1
print('(' * cnt2 + s + ')' * cnt1)


n = input()
cnt = 0
S = input()
m = 0
for s in S:
	if s == '(':
		cnt += 1
	else:
		cnt -= 1
	m = min(m, cnt)
left = -min(0, m)
right = abs(cnt - m)
print('(' * left + S + ')' * right)


import sys
input = sys.stdin.readline
n = int(input())
S = input().rstrip()
b = 0
q = 0
for s in S:
	if s == '(':
		b += 1
	elif b > 0:
		b -= 1
	else:
		q += 1
print('(' * q + S + ')' * b)


import math
from math import gcd, pi, sqrt
INF = float('inf')
import sys
sys.setrecursionlimit(10 ** 6)
import itertools
from collections import Counter, deque

def i_input():
	return int(input())

def i_map():
	return list(map(int, input().split()))

def i_list():
	return list(i_map())

def i_row(N):
	return [i_input() for _ in range(N)]

def i_row_list(N):
	return [i_list() for _ in range(N)]

def s_input():
	return input()

def s_map():
	return input().split()

def s_list():
	return list(s_map())

def s_row(N):
	return [s_input for _ in range(N)]

def s_row_str(N):
	return [s_list() for _ in range(N)]

def s_row_list(N):
	return [list(s_input()) for _ in range(N)]

def main():
	n = i_input()
	s = input()
	l = 0
	r = 0
	for i in s:
		if i == ')' and r > 0:
			r -= 1
		elif i == ')':
			l += 1
		if i == '(':
			r += 1
	print('(' * l + s + ')' * r)

def __starting_point():
	main()
__starting_point()


N = int(input())
S = input()
(L, R) = (0, 0)
for i in S:
	if i == '(':
		R += 1
	elif R:
		R -= 1
	else:
		L += 1
print('(' * L + S + ')' * R)


N = int(input())
S = input()
a = 0
b = 0
sub = 0
for i in range(N):
	if S[i] == '(':
		a += 1
	else:
		b += 1
	if a - b <= sub:
		sub = a - b
S = '(' * max(-sub, 0) + S + ')' * max(a - b - sub, 0)
print(S)


n = int(input())
S = input()
x = y = 0
for (i, s) in enumerate(S):
	y = y - 1 if s == '(' else y + 1
	x = max(x, y)
print('(' * x + S + ')' * (x - y))


N = int(input())
S = input()
s = S[:]
while '()' in s:
	s = s.replace('()', '')
r = s.count('(')
l = s.count(')')
print('(' * l + S + ')' * r)


n = int(input())
s = list(str(input()))
x = 0
y = 0
for i in range(n):
	if s[i] == '(':
		x += 1
	if s[i] == ')':
		if x >= 1:
			x -= 1
		else:
			y += 1
for _ in range(x):
	s.append(')')
for _ in range(y):
	s.insert(0, '(')
ans = ''.join(s)
print(ans)


n = int(input())
s = input()
z = s
while '()' in s:
	s = s.replace('()', '')
print('(' * s.count(')') + z + ')' * s.count('('))


N = int(input())
X = 0
S = input()
(T, U) = ('', '')
for i in range(N):
	if S[i] == '(':
		X += 1
	elif X == 0:
		T += '('
	else:
		X -= 1
U = ')' * X
print(T + S + U)


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


import sys, math, re
from functools import lru_cache
from collections import defaultdict
sys.setrecursionlimit(500000)
MOD = 10 ** 9 + 7

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

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

def ii():
	return int(input())

def i2(n):
	tmp = [list(mi()) for i in range(n)]
	return [list(i) for i in zip(*tmp)]

def main():
	N = ii()
	S = input()
	l = [0]
	for i in range(N):
		if S[i] == '(':
			l.append(l[-1] + 1)
		else:
			l.append(l[-1] - 1)
	m = min(l)
	if m < 0:
		l = list(map(lambda x: x - m, l))
	print('(' * l[0] + S + ')' * l[-1])

def __starting_point():
	main()
__starting_point()


N = int(input())
s = input()
keep = 0
ans = ''
for i in range(N):
	if s[i] == '(':
		ans += '('
		keep += 1
	elif keep > 0:
		ans += ')'
		keep -= 1
	else:
		ans = '(' + ans + ')'
print(ans + ')' * keep)


n = int(input())
s = input()
l = len(s)
d_l = [0] * (l + 1)
for i in range(1, l + 1):
	d = s[:i]
	n_open = d.count('(')
	d_l[i] = 2 * n_open - i
x = min(d_l)
print('(' * -x + s + ')' * (d_l[-1] - x))


import sys
sys.setrecursionlimit(10 ** 9)

def int1(x):
	return int(x) - 1

def II():
	return int(input())

def MI():
	return list(map(int, input().split()))

def MI1():
	return list(map(int1, input().split()))

def LI():
	return list(map(int, input().split()))

def LI1():
	return list(map(int1, input().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def MS():
	return input().split()

def LS():
	return list(input())

def LLS(rows_number):
	return [LS() for _ in range(rows_number)]

def printlist(lst, k=' '):
	print(k.join(list(map(str, lst))))
INF = float('inf')
from collections import deque

def solve():
	N = II()
	S = LS()
	q = deque([])
	cnt = 0
	for s in S:
		if s == '(':
			cnt += 1
			q.append(s)
		elif cnt >= 1:
			q.append(s)
			cnt -= 1
		else:
			q.appendleft('(')
			q.append(s)
	for _ in range(cnt):
		q.append(')')
	printlist(q, '')

def __starting_point():
	solve()
__starting_point()


N = int(input())
S = input()
(c1, c2) = (0, 0)
for s in S:
	if s == '(':
		c1 += 1
	elif c1 > 0:
		c1 -= 1
for s in reversed(S):
	if s == ')':
		c2 += 1
	elif c2 > 0:
		c2 -= 1
print('(' * c2 + S + ')' * c1)


input()
s = input()
L = R = 0
for t in s:
	if t == '(':
		R += 1
	elif R:
		R -= 1
	else:
		L += 1
print('(' * L + s + ')' * R)


N = input()
cnt = 0
s = ''
for x in input():
	if x == '(':
		cnt += 1
	else:
		cnt -= 1
		if cnt < 0:
			cnt += 1
			s = '(' + s
	s += x
for _ in range(cnt):
	s += ')'
print(s)