Problem:
 Score : 400 points    Problem Statement 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 1 3
())      Sample Output 1 (())       Sample Input 2 6
)))())      Sample Output 2 (((()))())       Sample Input 3 8
))))((((      Sample Output 3 (((())))(((())))

Solution (Python):


import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Prim(g):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = list(set(V))

    used = set([])
    q = []
    heapq.heappush(q, (0, V[0]))

    ret = 0
    while q:
        c, v = heapq.heappop(q)

        if v in used:
            continue
        used.add(v)
        ret += c
        for u in g[v]:
            heapq.heappush(q, (g[v][u], u))
    return ret


@mt
def slv(S):
    S = [c for c in S]
    l = []
    r = []
    la = []
    for c in S:
        if c == ')':
            if l:
                l.pop()
            else:
                la.append('(')
        else:
            l.append('(')
    S = la + S + [')' for _ in range(len(l))]
    return ''.join(S)


def main():
    N = read_int()
    S = read_str().strip()

    print(slv(S))


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
S = input()

sm = 0
L = 0
s_list = list(S)

for s in s_list:
    if s == "(":
        sm += 1
    else:
        sm -= 1
        if sm < 0:
            L += 1
            sm = 0
            
S = L*"(" + S

r_num = S.count(")")
l_num = S.count("(")

L = max(0, r_num-l_num)
R = max(0, l_num-r_num)


S = L*"(" + S + R*")"
print(S)

Solution (Python):
def main():
    n, s = int(input()), input()

    cnt, f = 0, 0
    for i in range(n):
        if s[i] == "(":
            cnt += 1
        else:
            cnt -= 1
            if cnt < 0:
                f += 1
                cnt = 0

    ans = f * "(" + s + cnt * ")"
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque


def check(s):
    x = 0
    for i in range(len(s)):
        if s[i] == "(":
            x += 1
        else:
            x -= 1

        if x < 0:
            return False

    if x == 0:
        return True
    else:
        return False


def main():
    n, s = int(input()), input()

    ss, q = "", deque()
    for i in range(len(s)):
        if s[i] == "(":
            ss += "("
        else:
            if len(ss) != 0:
                ss += ")"
                if check(ss):
                    q.append(ss)
                    ss = ""
            else:
                ss = "("
                while len(q) != 0:
                    ss += q.popleft()
                ss += ")"
                q.append(ss)
                ss = ""

    if len(ss) != 0:
        c = 0
        for i in range(len(ss)):
            if ss[i] == "(":
                c += 1
            else:
                c -= 1
        ss += ")" * c

    s = ""
    while len(q) != 0:
        s += q.popleft()

    print(s+ss)


if __name__ == '__main__':
    main()

Solution (Python):
x=int(input())
y=input()
A=[]
for i in range(0,x):
  if y[i]=='(':
    A.append(1)
  elif y[i]==")":
    A.append(-1)

st=0

s=0
for i in A:
  if s==0 and i==-1:
    st+=1
  else:
    s+=i

out=''
for i in range(0,st):
  out+='('
for j in A:
  if j==1:
    out+='('
  elif j==-1:
    out+=')'
for i in range(0,s):
  out+=')'
print(out)

Solution (Python):
n=int(input())
code=input()
fump=[code[i:i+1] for i in range(0,len(code))]
jump=[]
k=0
l=0
for i in range(n):
    if fump[i]=='(':
        jump.append('(')
        k+=1
    elif k>l:
        jump.append(')')
        l+=1
    else:
        jump.append(')')
        jump.insert(0,'(')
        k+=1
        l+=1
while k>l:
    jump.append(')')
    l+=1
for z in range(len(jump)):
    print(jump[z],end='')

Solution (Python):
n=int(input())
s=input()
ss=s
x=0
while x<len(ss)-1:
    if ss[x]=='(' and ss[x+1]==')':
        ss=ss[:x]+ss[x+2:]
        x=0
    else:
        x+=1
left=0
right=0
for i in ss:
    if i=='(':
        right+=1
    elif i==')':
        left+=1
q='('*left
w=')'*right
print(q+s+w)

Solution (Python):
N = int(input())
S = input()
Stack = ""
for s in S:
    Stack += s
    while len(Stack) >= 2:
        if Stack[-2:] == "()":
            Stack = Stack[:-2]
        else:
            break
c = Stack.count(")")
print("(" * c + S + ")" * (len(Stack) - c))

Solution (Python):
N = int(input())
S = input()

S_ans = S
count = 0
for i in range(N):
    if S[i]=="(": 
        if i>=1 and S[i-1]==")": 
            if count<0:
                S_ans = ("("*abs(count))+S_ans
                count = 0
        count += 1
    else: 
        count -= 1
    
        
if count > 0:
    S_ans = S_ans+(")"*abs(count))
else:
    S_ans = ("("*abs(count))+S_ans
    
print(S_ans)

Solution (Python):
N = int(input())
S = input()

op = 0
add_op = 0
for c in S:
    if c == '(': op += 1
    else: op -= 1
    if op < 0:
        add_op += 1
        op += 1
S = '('*add_op + S

cl = 0
add_cl = 0
for c in S[::-1]:
    if c == ')': cl += 1
    else: cl -= 1
    if cl < 0:
        add_cl += 1
        cl += 1
S += ')'*add_cl

print(S)

Solution (Python):
N = int(input())
S = input()

cnt = 0
left = 0
for i in range(N):
	if S[i] == '(':
		cnt += 1
	else:
		if cnt == 0:
			left += 1
		else:
			cnt -= 1

ans = ("("*left) + S + ")"*cnt
print(ans)

Solution (Python):
a=input()
s=input()
s2=0
while s2!=s:
    count=0
    s2=s
    for i in s:
        if i=='(': count+=1
        elif i==')': count-=1
        if count<0: 
            s='('+s
            break
    count=0
    for i in s[::-1]:
        if i==')': count+=1
        elif i=='(': count-=1
        if count<0: 
            s=s+')'
            break
print(s)

Solution (Python):
N = int(input())
s = input()
hist = [(0, 0)]
max_dist = 0
for v in s:
    x, y = hist[-1]
    if v == "(": x += 1
    elif v == ")": y += 1
    hist.append((x,y))
    max_dist = max(y - x, max_dist)
lastx , lasty = hist[-1]
print ("(" * max_dist + s + ")" *(lastx - lasty + max_dist))

Solution (Python):
n=int(input())
s=input()


ev=[0]
for c in s:
    if c=='(':
        ev.append(ev[-1]+1)
    else:
        ev.append(ev[-1]-1)
lowest = -min(ev)


numL = lowest + s.count('(')
numR = s.count(')')

Left = lowest
Right = numL-numR

for i in range(Left):
    print('(',end="")
print(s,end="")
for i in range(Right):
    print(')',end="")
print()

Solution (Python):
n = int(input())
s = input()
ans = ""
cur = 0
for i in s:
  if i == "(":
    cur += 1
    ans += i
  else:
    if cur:
      ans += i
      cur -= 1
    else:
      ans = "(" + ans + i
ans += ")" * cur
print(ans)

Solution (Python):
def m():
    n = int(input())
    s = str(input())
    exleft = 0
    exright = 0
    for c in s:
        if c == "(":
            exleft +=1

        elif c == ")":
            if exleft <= 0:
                exright +=1
            else:
                exleft -=1
    return "(" * exright + s + ")" * exleft

print(m())

Solution (Python):
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*')')

Solution (Python):
N = int(input())
S = list(input())

mae = S.count("(")
ushiro = N - mae

p_sum = [0] * N

if S[0] == "(":
	p_sum[0] = 1
else:
	p_sum[0] = -1

for i in range(1, N):
	if S[i] == "(":
		p_sum[i] = p_sum[i - 1] + 1
	else:
		p_sum[i] = p_sum[i - 1] - 1

def Good(x):
	if min(x) >= 0 and mae == ushiro:
		return True
	else:
		return False

if not Good(p_sum):
	S = ["("] * (- min(0, min(p_sum))) + S + [")"] * (mae - ushiro - min(0, min(p_sum)))

print("".join(S))

Solution (Python):
N = int(input())
S = input()

T = 0
ans = []

for s in S:
    if s == "(":
        T += 1
        ans.append("(")
    else:
        T -= 1
        ans.append(")")
        if T < 0:
            ans.insert(0, "(")
            T = 0

for i in range(T):
    ans.append(")")
print("".join(ans))

Solution (Python):
n=int(input())
a=input().strip()
x=0
b=[]
for ai in [i for i in list(a)]:
  if ai=='(':
    x+=1
  else:
    x-=1
  b.append(x)
l=b[len(b)-1]	
if min(b)< 0:
  a = '(' * abs(min(b)) + a
  l+=abs(min(b))
a=a+')'*l
    
print(a)

Solution (Python):
n = int(input())
s = input()
list_s = list(s)
cnt = 0

for si in list_s:
    if si == ')':
        if cnt <= 0:
            s = '(' + s
        else :
            cnt -= 1
    
    if si == '(':
        cnt += 1
    
for _ in range(cnt):
    s += ')'

print(s)

Solution (Python):
N=int(input())
S=input()
cnt=0
ansP=0
ansA=0
for i in range(N):
  if cnt==0 and S[i]==')':
    ansP+=1
  elif cnt>0 and S[i]==')':
    cnt-=1
  else:
    cnt+=1

cnt=0
Sans=S[::-1]
for i in range(N):
  if cnt==0 and Sans[i]=='(':
    ansA+=1
  elif cnt>0 and Sans[i]=='(':
    cnt-=1
  else:
    cnt+=1

print("("*ansP+S+")"*ansA)

Solution (Python):
N = int(input())
S = input()
L,R,x = 0,0,0
for i in range(N):
    if x == 0:
        if S[i]==")":
            L += 1
        else:
            R += 1
            x += 1
    else:
        if S[i]==")":
            R -= 1
            x -= 1
        else:
            R += 1
            x += 1
print("("*L + S + ")"*R)

Solution (Python):
n = int(input())
s = input()
mi = 0
t = 0
for i in s:
    if i == '(':
        t+=1;
    else:
        t-=1;
        mi = min(mi,t)
if mi<0:
    print('('*-mi,end='')
    print(s+')'*(t-mi))
else:
    print(s+')'*t)

Solution (Python):
N = int(input())
S = list(input())

count_end = 0
count = 0
for s in S:
    if s == ')':
        if count > 0:
            count -= 1
        else:
            count_end += 1
    else:
        count += 1

count_begin = 0
count = 0
S.reverse()
for s in S:
    if s == '(':
        if count > 0:
            count -= 1
        else:
            count_begin += 1
    else:
        count += 1
S.reverse()
print (("("*count_end) + "".join(S) +  (")"*count_begin))

Solution (Python):
n = int(input())
s = input()
a,b,c,d,x = 0,0,0,0,s
for i in s:
	if i=="(": a+=1
	else: b+=1
	if a<b:
		x = "("+x
		a+=1
x = x[::-1]
answer = x
for i in x:
	if i==")": c+=1
	else: d+=1
	if c<d:
		answer = ")"+answer
		c+=1
answer = answer[::-1]
print(answer)

Solution (Python):
from collections import deque
N = int(input())
S = list(input())
A = deque()
B = []

left_cnt = 0
right_cnt = 0
for s in S:
    if s == "(":
        left_cnt += 1
        A.append("(")
    else:
        A.append(")")
        if right_cnt + 1 > left_cnt:
            B.append("(")
        else:
            right_cnt += 1

C = [")"] * (left_cnt - right_cnt)
B.extend(A)
B.extend(C)
print("".join(B))

Solution (Python):
n = int(input())
s = input()
cnt = [0, 0]
add = [0, 0]
ans = ''
for i in range(n):
    if s[i] == ')':
        cnt[0] += 1
        if cnt[0] > cnt[1]:
            add[1] += 1
            cnt[1] += 1
    else:
        cnt[1] += 1

print('(' * add[1] + s + ')'*(cnt[1] -cnt[0]))

Solution (Python):
N=int(input())
S=input()
T=S
M=len(T)
while(True):
    T=T.replace("()","")
    if len(T)==M:
        break
    else:
        M=len(T)
k=0
for j in T:
    if j==")":
        k+=1
    else:
        break
print("("*k+S+")"*(M-k))

Solution (Python):
n = int(input())
s = list(input())
now = 0
unclosen = 0
opened = 0
for i in s:
    if i == ")":
        now -= 1
        if opened:
            opened -= 1
        else:
            unclosen += 1
    else:
        now += 1
        opened += 1
print("(" * unclosen + "".join(s) + ")" * opened)

Solution (Python):
import numpy as np
n = int(input())
s = list(input())
j = []
now = 0
unclosen = 0
opened = 0
for i in s:
    if i == ")":
        now -= 1
        if opened:
            opened -= 1
        else:
            unclosen += 1
    else:
        now += 1
        opened += 1
j = np.array(j)
print("(" * unclosen + "".join(s) + ")" * opened)

Solution (Python):
N = int(input())
S = list(input())
S_2 = S[:]
prev = 0
cnt = 0
new_str = []
for i in range(len(S)):
	if S[i] == '(':
		cnt += 1
	else:
		cnt -= 1

	if cnt < 0:
		S_2.insert(0,'(')
		cnt += 1


if cnt > 0:
	for i in range(cnt):
		S_2.append(')')

print(''.join(S_2))

Solution (Python):
def d_Insertion(N, S):
    
    d = 0
    x = 0
    for c in S:
        if c == '(':
            d += 1
        else:
            d -= 1
        x = min(x, d)
    ans = '(' * (-x) + S + ')' * (d - x)
    return ans

N = int(input())
S = input().strip()
print(d_Insertion(N, S))

Solution (Python):
n = int(input())
s = input()


def walk(s):
    """
        Assume that
            up ... '('
            down ... ')'
            start with height 0
            record lowest, endsup.
    """
    height = 0
    lowest = 0
    for x in s:
        if x == '(':
            height += 1
        elif x == ')':
            height -= 1
            lowest = min(height, lowest)
        else:
            pass
    return height, lowest

def inserter(s, height, lowest):
    return '(' * abs(lowest) + s + ')' * (height- lowest)

h, low = walk(s)
print(inserter(s, h, low))

Solution (Python):
N = int(input())
s = input()
p = 0
ans = ''
for c in s:
    if c == '(':
        p += 1
    elif c == ')':
        p -= 1
    if p == -1:
        p = 0
        ans = '(' + ans + c
    else:
        ans = ans + c

ans += ')' * p
print(ans)

Solution (Python):
def wrong(s):
    c = 0

    for x in s:
        if(x == '('):
            c += 1
        elif(x == ')'):
            c -= 1

        if(c < 0):
            return c

    return c

n = int(input())
s = input()

w = wrong(s)

while(w):
    if(w > 0):
        s = s + ')'
    elif(w < 0):
        s = '(' + s

    w = wrong(s)

print(s)

Solution (Python):
from collections import Counter
n = int(input())
s = input()
c = Counter(s)
ds = c['('] - c[')']
x = min([Counter(s[:i])['('] - Counter(s[:i])[')'] for i in range(n+1)])
print('(' * (-1*x) + s + ')' * (ds - x))

Solution (Python):
def main():
    n = input()
    S = input()
    cnt = 0
    m = 0
    for s in S:
        if s == '(':
            cnt += 1
        else:
            cnt -= 1
        
        if cnt < 0:
            m += 1
            cnt += 1
            
    ans = "("*m+S+")"*cnt
    print(ans)
    
if __name__ == "__main__":
    main()

Solution (Python):

"""
http://abc064.contest.atcoder.jp/tasks/abc064_d

"""
import sys
from sys import stdin
input = stdin.readline


def check_balance(S):
    st = 0
    for pos, c in enumerate(S):
        if c == '(':
            st += 1
        else:                   
            st -= 1
            if st < 0:
                break
    return st


def main(args):
    N = int(input())
    S = input().strip()
    

    result = check_balance(S)
    while result != 0:
        if result < 0:
            S = '(' + S
        elif result > 0:
            S = S + ')'
        result = check_balance(S)

    print(S)

if __name__ == '__main__':
    main(sys.argv[1:])

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

Solution (Python):
N = int(input())
S = input()

Sold = S
while True:
    Snew = Sold.replace('()', '')
    if len(Snew) == len(Sold):
        break
    Sold = Snew

num = Snew.count(')')
print('(' * num + S + ')' * (len(Snew) - num))

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

print('('*L+N+')'*R)

Solution (Python):
N = int(input())
S = input()

c,L,R = 0,0,0
for i in range(N):
    if S[i] == "(":
        c += 1
    else:
        c -= 1
    if c < 0:
        L += 1
        c = 0

c = 0
for i in range(N-1,-1,-1):
    if S[i] == ")":
        c += 1
    else:
        c -= 1
    if c < 0:
        R += 1
        c = 0

print(L*"(" + S + R*")")

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

Solution (Python):
n = int(input())
s = input()

unpair = 0
left = 0
right = 0
for c in s:
    if(c == "("):
        unpair += 1
    else:
        if(unpair):
            unpair -= 1
        else:
            left += 1
right = unpair

print("(" * left + s + ")" * right)

Solution (Python):
N = int(input())
S = input()

a = 0
b = 0

for s in S:
    if s == "(":
        a += 1
    else:
        if a > 0:
            a -= 1
        else:
            b += 1
            
print("("*b + S + ")"*a)

Solution (Python):
n = input()
s = input()

def count(s, k):
    c, needs = 0, 0
    for i in s:
        if i != k:
            if c <= 0:
                needs += 1
            else:
                c -= 1
        else:
            c += 1
    return needs

l = count(s, '(')
r = count(s[::-1], ')')
print('('*l + s + ')'*r)

Solution (Python):
n=int(input())
s=input()
stack=[]
l=0
r=0
for c in s:
    if len(stack)>0 and stack[-1]=='(' and c==')':
        stack.pop()
    else:
        stack.append(c)
if len(stack)==0:
    print(s)
else:
    for c in stack:
        if c==')':
            l+=1
        else:
            r+=1
    print('('*l+s+')'*r)

Solution (Python):
from collections import defaultdict


def main():
    N = int(input())
    S = input()
    t = S[:]
    while True:
        change = False
        for i in range(1, len(t)):
            if (t[i - 1], t[i]) == ("(", ")"):
                t = t[:i - 1] + t[i + 1:]
                change = True
                break
        if not change:
            break

    a = "(" * t.count(")")
    b = ")" * t.count("(")
    print(a + S + b)


if __name__ == '__main__':
    main()

Solution (Python):
input_line_1 = raw_input()
input_line_2 = raw_input()

count_1 = 0
count_2 = 0
for kigou in input_line_2:
	if kigou == "(":
		count_2 += 1
	if kigou == ")":
		if count_2 > 0:
			count_2 -= 1
		else:
			count_1 += 1
	
print count_1 * "(" + input_line_2 + count_2 * ")"

Solution (Python):
N = int(input())
S = str(input())

def count_need(string, from_left=True):
    savings = 0
    ng = 0
    
    if from_left == False:
        key = '('
    else :
        key = ')'

    for s in string:
        if (s == key):
            if savings <= 0: 
                ng += 1
            else:
                savings -= 1
        else:
            savings += 1
    return ng

left_num = count_need(S, from_left=True)
right_num = count_need(S[::-1], from_left=False)

print("("*left_num + S + ")"*right_num)

Solution (Python):
import sys

stdin = sys.stdin

ns = lambda: stdin.readline()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

N = ni()
S = ns().strip()

d = 0
mind = 0

for i in range(len(S)):
    if(S[i] == '('):
        d += 1
    else:
        d -= 1
    mind = min(mind,d)
print ('('*(-mind) + S + ')'*(d-mind))

Solution (Python):
N = int(raw_input())
a = raw_input()

b = list(a)
check = 0
j = 0
k = 0
for i in range(N):
	if b[i] == "(":
		check = check + 1
	else:
		check = check - 1
	
	if check < 0:
		j += 1
		check = check + 1
for i in range(j):
	b = ["("] + b

for i in range(check):
	b = b + [")"]
	k += 1
import six
for i in range(N+j+k):
	six.print_(b[i],end = "")

Solution (Python):
n = int(input())
str = input()
 
r = 0
l = 0
i = 0
 
while i < n:
    if str[i] == '(':
        l += 1
        i += 1
    elif str[i] == ')' and l == 0:
        str = '(' + str
        n += 1
        i += 2
    else:
        l -= 1
        i += 1
 
if l > 0:
    while l > 0:
        str = str + ')'
        l -= 1
 
print(str)

Solution (Python):
n = input()
str = raw_input()

r = 0
l = 0
i = 0

while i < n:
    if str[i] == '(':
        l += 1
        i += 1
    elif str[i] == ')' and l == 0:
        str = '(' + str
        n += 1
        i = 0
    else:
        l -= 1
        i += 1

if l > 0:
    while l > 0:
        str = str + ')'
        l -= 1

print str

Solution (Python):
N=int(input())
s=input()

lc=0
rc=0
for brc in s:
    if brc=='(':
        lc+=1
    elif brc==')':
        if lc>0:
            lc-=1
        else:
            rc+=1
            
retVal=""
for i in range(rc):
    retVal+='('
retVal+=s
for i in range(lc):
    retVal+=')'
print(retVal)

Solution (Python):
N = int(input())
S = input()

head = 0
tail = 0

for i in S:
    if i == "(":
        head += 1
    elif head > 0:
        head -= 1
    else:
        tail += 1

res = tail * "(" + S + head * ")"
print(res)

Solution (Python):
import copy


def get_completed(s):
    ans = copy.deepcopy(s)

    not_close = 0
    not_open = 0

    for c in s:
        if c == '(':
            not_close += 1

        if c == ')':
            if not_close > 0:
                not_close -= 1
            else:
                not_open += 1

    for i in range(not_open):
        ans = '(' + ans

    for i in range(not_close):
        ans = ans + ')'

    return ans


if __name__ == '__main__':
    N = input()
    S = input()

    print(get_completed(S))

Solution (Python):
n = input()
s = input()
count = 0
countl = 0
for c in s:
    if c=='(':
        count += 1
    else:
        count -= 1
    if count < 0:
        countl += 1
        count = 0
count = 0
countr = 0
for c in s[::-1]:
    if c=='(':
        count -= 1
    else:
        count += 1
    if count < 0:
        countr += 1  
        count = 0
print('('*countl + s + ')'*countr)

Solution (Python):





number = int(input())
strings = input()




while True:
    counter = 0

    for s in strings:
        if s == "(":
            counter += 1
        else:
            if counter > 0:
                counter -= 1
            else:
                strings = "(" + strings
                counter = -1
                break
        
    if counter > 0:
        strings = strings + ")" * counter
        
    if counter == 0:
        break

print(strings)

Solution (Python):
import sys


if __name__ == "__main__":
    N = raw_input()
    S = raw_input()

    bra = 0
    ket = 0
    pair = 0
    
    for s in S:
        if s == '(':
            bra += 1
        else:
            if bra > 0:
                bra -= 1
                pair +=1
            else:
                ket += 1
    print '(' * ket + S + ')'*bra

Solution (Python):

x = int(input())
y = input()

z = y

while z.find("()") != -1:
    z = z.replace("()","")

a = z.count("(")
b = z.count(")")

ans = y

for i in range(a):
    ans = ans + ")"

for i in range(b):
    ans = "(" + ans

print(ans)

Solution (Python):


N = input()
S = raw_input()



chars=list(S)


sum=0
for i in chars:
	if i == "(":
		sum+=1
		
	elif i== ")":
		sum-=1
		
		if sum<0:
			S="("+S
			sum=0

S=S+")"*sum

print S

Solution (Python):
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)

Solution (Python):
N = input()
ss = raw_input()
s=ss.split("()")

while len(s)>1:
    s="".join(s)
    
    s=s.split("()")

a=""
b=""

s=s[0]
N=len(s)



for i in range(N):
    if s[i]=="(":
        a+=")"
    if s[i]==")":
        b+="("

print(b+ss+a)

Solution (Python):


import sys
import math

N, = map(int, sys.stdin.readline().rstrip().split())
S = sys.stdin.readline().rstrip()

def is_fullfilled(in_str):
    LR = 0
    for c in in_str:
        if LR < 0:
            return False
        if c == "(":
            LR += 1
        else:
            LR -= 1
    if LR == 0:
        return True
    else:
        return False


LR = 0
for c in S:
    if c == "(":
        LR += 1
    else:
        LR -= 1

while LR < 0:
    S = "(" + S
    LR += 1
while LR > 0:
    S = S + ")"
    LR -= 1

while not is_fullfilled(S):
    
    S = "(" + S + ")"

print(S)

exit(0)

Solution (Python):
N=input()
brac = raw_input()
ans = brac

while '()' in brac:
	brac=brac.replace('()','')

left=brac.count('(')
right=brac.count(')')

print '('*right +ans +')'*left

Solution (Python):

N = int(raw_input())
S = raw_input()

n = 0
m = 0
for s in S:
	if s == '(':
		n += 1
	else:
		n -= 1
	m = min(n, m)

l = abs(m)
r = n + l

S = '(' * l + S + ')' * r
print S

Solution (Python):
input()

s = raw_input().strip()

l = "("
r = ")"

l_c = 0
r_c = 0
for c in s:
    if c == l:
        l_c+=1
    elif c == r:
        if l_c>0:
            l_c-=1
        else:
            r_c+=1
            
print "(" * r_c + s + ")" * l_c

Solution (Python):
input()
gt =input()
gtt = gt
for i in range(100):
    gt = gt.replace("()","",2)

num1 = gt.count("(")
num2 = gt.count(")")
print("("*num2+gtt+")"*num1)

Solution (Python):
N=int(input())
S=input()
open=0
output=S
for c in S:
    if c=="(":
        open=open+1

    else:
        if open>0:
            open=open-1
        else:
            output="("+output

for i in range(open):
    if open>0:
        output=output+")"

print(output)

Solution (Python):
n = int(input())
a = list(input())
b = []
cou1=0

for i in a:
    if i=="(":
        cou1 += 1
        b.append("(")
    else:
        b.append(")")
        if cou1==0:
            b.insert(0,"(")
            continue
        cou1 -= 1

for _ in range(cou1):
    b.append(")")

print(*b,sep='')

Solution (Python):
N = int(input())
S = input()
left = 0
right = 0
score = 0
for i in range(len(S)):
    if(S[i] is "("):
        if(score < 0):
            left -= score
            score = 1
        else:
            score += 1
    else:
        score -= 1

if(score < 0):
    left -= score
else:
    right += score

for i in range(left):
    S = "(" + S
for i in range(right):
    S = S + ")"
print(S)

Solution (Python):
N = input()
string = input()
arrange = string
while True:
    after_arrange = arrange.replace('()','')
    if after_arrange == arrange:
        break
    arrange = after_arrange
left = after_arrange.count(')')
right = after_arrange.count('(')
print('('*left+string+')'*right)

Solution (Python):
N = int(input())
S = input()

output = ''

hiraki = 0
for i in S:
    if i == '(':
        hiraki += 1
        output += i
    else:
        if hiraki > 0:
            hiraki -= 1
            output += i
        else:
            output = '(' + output
            output += i

output += ')' * hiraki

print(output)

Solution (Python):
n = int(input())
l = input()

s = ""
left = 0
right = 0

for a in l:
	if a == "(":
		left += 1
	else:
		if left <= right:
			s = "(" + s
			left += 1
		right += 1
	s += a

if left - right < 0:
	for x in range(right - left):
		s = "(" + s
else:
	for x in range(left - right):
		s += ")"

print (s)

Solution (Python):
N = int(input())
S = list(input())
Out =  S[:]
while len(S) > 0:
	if S[0] == ")":
		Out.insert(0,"(")
		del S[0]
	elif S[0] == "(":
		for j in range(len(S)):
			if S[j] == ")":
				del S[j]
				del S[0]
				break
			elif j == len(S) - 1 :
				Out.append(")")
				del S[0]
print(''.join(Out))

Solution (Python):
N = int(input())
S = list(input())
Out =  S[:]
while len(S) > 0:
	if S[0] == ")":
		Out.insert(0,"(")
		del S[0]
	elif S[0] == "(":
		i = 0
		for j in range(len(S)):
			if S[j] == ")":
				del S[j]
				del S[0]
				i += 1
				break
			elif j == len(S) - 1 :
				Out.append(")")
				del S[0]
print(''.join(Out))

Solution (Python):
N = int(input())
S = input()

output = ''

hiraki = 0
toji = 0
for i in S:
    if i == '(':
        if toji > 0:
            output = '(' * toji + output
            toji = 0
            hiraki += 1
            output += i
        else:
            hiraki += 1
            output += i
    else:
        if hiraki > 0:
            hiraki -= 1
            output += i
        else:
            toji += 1
            output += i

output += ')' * hiraki
output = '(' * toji + output

print(output)

Solution (Python):
N = int(input())
S = list(input())
Out =  S[:]
Temp = S[:]
while len(Temp) > 0:
	if Temp[0] == ")":
		Out.insert(0,"(")
		del Temp[0]
	elif Temp[0] == "(":
		i = 0
		for j in range(len(Temp)):
			if Temp[j] == ")":
				del Temp[j]
				del Temp[0]
				i += 1
				break
		if i == 0:
			Out.append(")")
			del Temp[0]
print(''.join(Out))

Solution (Python):
N = int(input())
S = input()

output = ''

hiraki = 0
toji = 0
for i in S:
    if i == '(':
        if toji > 0:
            output = '(' * toji + output
            output += ')' * toji
            toji = 0
            hiraki += 1
            output += i
        else:
            hiraki += 1
            output += i
    else:
        if hiraki > 0:
            hiraki -= 1
            output += i
        else:
            toji += 1

for i in range(hiraki):
    output += ')'

for i in range(toji):
    output += ')'

output = '(' * toji + output

print(output)

Solution (Python):
N = int(input())
S = input()

score = 0
ln = 0
rn = 0

for s in S:
    if s == '(':
        score += 1
    elif s == ')':
        score -= 1

    if score < 0:
        ln += 1
        score = 0

if score > 0:
    rn = score
    score = 0

S = '('*ln + S + ')'*rn
print(S)

Solution (Python):
input()
s = input().strip()
stock, depth = 0, 0
for c in s:
    if c == '(':
        depth += 1
    else:
        if depth:
            depth -= 1
        else:
            stock += 1
print('(' * stock + s + ')' * depth)

Solution (Python):
input()
s = input().strip()
ans = s
depth = 0
for c in s:
    if c == '(':
        depth += 1
    else:
        if depth:
            depth -= 1
        else:
            ans = '(' + ans
ans += ')' * depth
print(ans)

Solution (Python):
n = int(raw_input())
s = raw_input()
ct = 0
mn = 0
for c in s:
    if c == '(':
        ct += 1
    else:
        ct -= 1
    mn = min(mn,ct)
l = abs(mn)
r = ct + l
s = '('*l + s + ')'*r
print s

Solution (Python):
n = int(raw_input())
s = raw_input()
ct = 0
mn = 0
for c in s:
    if c == '(':
        ct += 1
    else:
        ct -= 1
    mn = min(mn,ct)
s = '('*abs(mn) + s
ct = 0
for c in s:
    if c == '(':
        ct += 1
    else:
        ct -= 1
s = s + ')'*ct
print s