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):
N=int(input())
r=0
l=0
S = input()
li_S = []
count = 0

for i in range(N):
    if S[i]==")":
         r += 1
         li_S.append(")")
    else:
        l += 1
        li_S.append("(")
    if r > l :
        li_S.insert(0,"(")
        l += 1

for i in range(l-r):
    li_S.append(")")
print("".join(li_S))

Solution (Python):
N = input()
S = raw_input()
ans = ""
cnt = 0
for ch in S:
    if (cnt <= 0) and (ch == ")"):
        ans = "(" + ans
    elif (ch == ")"):
        cnt -= 1
    else:
        cnt += 1
    ans += ch
ans += ")" * cnt
print ans

Solution (Python):

import sys, re

N = input()
S = input()
sentence = ''
left, right = 0, 0
for s in S:
    sentence += s
    if s == '(':
        left += 1
    else:
        right += 1
    if left - right < 0:
        sentence = '(' + sentence
        left += 1
if left - right > 0:
    sentence = sentence + ')' * (left - right)
print(sentence)

Solution (Python):

import sys, re

N = input()
S = input()

sentence = ''
left, right = 0, 0

for s in S:
    sentence += s
    if s == '(':
        left += 1
    else:
        right += 1
    if left - right < 0:
        sentence = '(' + sentence
        left += 1
if left - right > 0:
    sentence = sentence + ')' * (left - right)
print(sentence)

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

Solution (Python):
n = int(input())
s = input()
head = ""
depth = 0
for i in s:
    if i == "(":
        depth += 1
    else:
        if depth == 0:
            head += "("
        else:
            depth -= 1
tail = "".join([")" for _ in range(depth)])
print(head + s + tail)

Solution (Python):
input()
s = input()
stk = list()
for c in s:
    if c == '(':
        stk.append('(')
    elif len(stk) != 0 and stk[-1] == '(':
        stk.pop()
    else:
        stk.append(')')
print(stk.count(')') * '(' + s + stk.count('(') * ')')

Solution (Python):
import sys



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

c = 0
m = 0
M = 0

for l in s:
    if l == '(':
        c += 1
    if l == ')':
        c -= 1
    if m > c:
        m = c
    if M < c:
        M = c

left = '(' * (-m)
c += -m
right = ')' * c
res = left + s + right
print(res)

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

cnt = 0

ans = []

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

if cnt > 0:
    for _ in range(cnt):
        ans.append(")")
elif cnt < 0:
    cnt = 0 - cnt
    for _ in range(cnt):
        ans.insert(0, "(")

print(''.join(ans))

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

cur = 0
pre = 0
for c in s:
    if c == '(':
        cur += 1
    else:
        cur -= 1

    if cur < 0:
        pre += 1
        cur += 1

print("("*pre + s + ")"*cur)

Solution (Python):
n = int(input())
s = input()
start = 0
end = 0

for i in range(n):
    if s[i] == "(":
        start += 1
    elif s[i] == ")" and start <= 0:
        end += 1
    else:
        start -= 1

print("("*end+s+")"*start)

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

Solution (Python):
N = int(input())
S = input()
begin = 0
end = 0
for i in range(N):
    if(S[i] == "(" ):
        begin += 1
    elif(S[i] == ")" and begin <= 0):
        end += 1
    else:
        begin -= 1
S = ("(" * end) + S + (")" * begin)
print(S)

Solution (Python):




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

def output(start, end):
    ans = ""
    for i in range(start):
        ans += "("
    for i in S:
        ans += i
    for i in range(end):
        ans += ")"
    return ans

stock = 0
lack_start = 0
lack_end = 0

for s in S:
    if s == '(':
        stock += 1
    elif s == ')':
        if stock > 0:
            stock -= 1
        else:
            lack_start += 1

lack_end = stock
print(output(lack_start, lack_end))

Solution (Python):


if __name__ == "__main__":
    N = int(input())
    string = input()

    right = 0
    left = 0

    for char in string:
        if char == '(':
            right += 1
        else:
            right -= 1

        if right == -1:
            left += 1
            right = 0

    L = '(' * left
    R = ')' * right

    print(L + string + R)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    s = S()
    d = collections.defaultdict(int)
    for c in s:
        d[c] += 1
    l = d['(']
    r = d[')']

    if l > r:
        s += ')' * (l-r)
    elif r > l:
        s = '(' * (r-l) + s

    c = 0
    rc = 0
    i = 0
    while i < len(s):
        if s[i] == '(':
            c += 1
        else:
            c -= 1
        if c < 0:
            rc += 1
            c = 0
        i += 1
    s = '(' * rc + s + ')' * rc
    return s


print(main())

Solution (Python):
n = int(input())
s = input()
bf = []
af = []
st = ['*']

for c in s:
    pre = st[-1]
    st.append(c)    

    if c ==  ')':
        if (pre == '(') :
            st.pop()
            st.pop()
            af.pop()
            continue
        bf.append('(')
    else:
        af.append(')')
ans = ''.join(bf) + s + ''.join(af)
print(ans)

Solution (Python):
from sys import stdin 
n = int(stdin.readline())
a = stdin.readline().strip()
x = 0
fir = 0 
sec = 0
for i in a:
    if i=='(':
        fir+=1
    else:
        if fir > 0:
            fir-=1
        else:
            sec+=1
            fir = 0

print sec*'(' + a + ')'*fir

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

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

    if acc == -1:
        l += 1
        acc += 1

L = '(' * l
R = ')' * acc
print (L + S + R)

Solution (Python):
n = int(input())
s = input()
stack_num = 0
ind = 0
ret = ""
nr = 0
for c in s:
    if(c == "("):
        stack_num += 1
    else:
        stack_num -= 1
    if(stack_num < 0):
        ret += "("
        stack_num += 1
if(stack_num < 0):
    ret += "(" * (-stack_num)
ret += s
if(stack_num >= 0):
    ret += ")" * stack_num
print(ret)

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

    s = S
    while s.count('()'):
        s = s.replace('()', '')

    if len(s) == 0:
        print(S)
        return

    left = ''
    right = ''
    if s[0] == ')':
        left = '(' * s.count(')')
    if s[-1] == '(':
        right = ')' * s.count('(')

    print('{}{}{}'.format(left, S, right))

main()

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

    s = S
    while True:
        s = s.replace('()', '')
        if s.count('()') == 0:
            break

    if len(s) == 0:
        print(S)
        return

    left = ''
    right = ''
    if s[0] == ')':
        left = '(' * s.count(')')
    if s[-1] == '(':
        right = ')' * s.count('(')

    print('{}{}{}'.format(left, S, right))

main()

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


n = ni()
s = ns()

level = 0
left = 0

for i in range(0, n):
    if s[i] == '(':
        level += 1
    else:
        level -= 1
    
    if level + left < 0:
        left += 1
    
level += left

print('(' * left + s[0:n] + ')' * level)

Solution (Python):
n = int(input())
S = input()
s = S[:]
while '()' in s:
	s = s.replace('()','')

print('('*s.count(')') + S + ')'*s.count('('))

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

v = []
tmp =[]

for s in S:
    if s == "(":
        tmp.append(")")
        v.append("(")
    else:
        if len(tmp) == 0:
            v.insert(0, "(")
            v.append(")")
        else:
            v.append(tmp.pop())

while tmp:
    v.append(tmp.pop())

print("".join(v))

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

Solution (Python):
time = int(input())
kakko = input()
hidarikakko = 0 
migikakko = 0 
hidariHuyasu = 0 
migiHuyasu = 0 

for i in range(time):
    if kakko[i] == "(":
        hidarikakko += 1
    else:
        if hidarikakko == 0:
            hidariHuyasu += 1
        else:
            hidarikakko -= 1

hidarikakko = 0 
migikakko = 0 
gyaku = range(time)


for i in reversed(range(time)):
    if kakko[i] == ")":
        migikakko += 1
    else:
        if migikakko == 0:
            migiHuyasu += 1
        else:
            migikakko -= 1
print("(" * hidariHuyasu + kakko + ")" * migiHuyasu)

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


v = []


stock = 0

for i in s:
    if i=="(":
        stock+=1
        v.append("(")
    else:
        if stock ==0:
            v.insert(0,"(")
            v.append(")")
        else:
            stock -= 1
            v.append(")")

for i in range(stock):
    v.append(")")

print(*v,sep='')

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

str1=str
str2=str
n=int(N/2)

for var in range(1,n+1):
    try:
        str1=str1.replace("()","")
    except:
        break

s1=str1.count("(")
s2=str1.count(")")

print("("*s2+str2+")"*s1)

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

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

y=[0]*N
left=''
right=''

for i in range(N):
    if (x[i]==')'):
        y[i]=-1
    else:
        y[i]= 1

for i in range(N):
    if y[i]==1:
        for j in range(i,N):
            if y[j]==-1:
                y[i]=y[j]=0
                break



for i in range(y.count(-1)):
    left=left+'('
for i in range(y.count(1)):
    right=right+')'

print(left+x+right)
        
quit()

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

stack=[]
stack2=[]
index=-1
index2=-1



for i in range(N):
    stack.append(S[i])
    index+=1

    if len(stack)==1 and stack[0]==')':
        del stack[0]
        index-=1

    elif stack[index-1]=='(' and stack[index]==')':
        stack.pop(index)
        stack.pop(index-1)
        index-=2
    

last=len(stack)
for i in range(last):
    S=S+")"



T=S[::-1]




leng=len(T)
for i in range(leng):
    stack2.append(T[i])
    index2+=1

    if len(stack2)==1 and stack2[0]=='(':
        del stack2[0]
        index2-=1

    elif stack2[index2-1]==')' and stack2[index2]=='(':
        stack2.pop(index2)
        stack2.pop(index2-1)
        index2-=2
    

first=len(stack2)
for i in range(first):
    T=T+"("


print(T[::-1])

Solution (Python):
N = input()
string = [x for x in input()]
strings = string[:]  
stack = []

for i in range(len(strings)):
    if strings[i] == '(':
        stack.append(1)
    elif strings[i] == ')':
        if not stack:
            string.insert(0,'(')
        else:
            stack.pop()

if stack:
    for i in range(len(stack)):
        string.append(')')

print(''.join(string))

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

Solution (Python):
a = int(input())
c = input()
nl = 0
nr = 0
for i in c :
    if i == ')' :
        nr += 1
        if nl > 0 :
            nr -= 1
            nl -= 1
    elif i == '(' :
        nl += 1
c = '('*nr + c + ')'*nl
print(c)

Solution (Python):
import sys

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

tries = []

def count(S):
    cnt = 0
    for i in S:
        if i == "(":
            cnt += 1
        else:
            cnt -= 1
    return cnt

def valid(S):
    cnt = 0
    for i in S:
        if i == "(":
            cnt += 1
        else:
            cnt -= 1
        if cnt < 0:
            return False
    return True

def bt(S):
    cnt = count(S)
    if count(S) == 0 and valid(S):
        tries.append(S)
        return
    else:
        if cnt < 0:
            return bt("(" + S)
        else:
            return bt(S + ")")
bt(s)
print(min(tries))

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

l=0
R=0
for sbk in bk:
    if sbk==')':
        if l==0:
            R+=1
        else:
            l-=1
    else:
        l+=1



r=0
L=0
for sbk in reversed(bk):
    if sbk=='(':
        if r==0:
            L+=1
        else:
            r-=1

    else:
        r+=1




res='('*R+"".join(bk)+')'*L
print(res)

Solution (Python):
n = int(input())
s = input()
copy = s
s_list = list(s)
left_list = []
right_list = []

n = len(s_list)
flag = 1
if len(s_list) > 1:
    while flag == 1:
        flag = 0

        if n>=1:
            for i in range(n-1):
                if s_list[i] == '(' and s_list[i+1] == ')':
                    s_list.pop(i)
                    s_list.pop(i)
                    n -= 2
                    flag = 1
                    break

        else:
            break




for word in s_list:
    if word == ')':
        left_list.insert(0,'(')
    else:
        right_list.insert(len(right_list),')')


word = ""

for lef in left_list:
    word += lef

word += s

for rig in right_list:
    word += rig

print(word)

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

right = 0
left = 0
sum_right = 0
sum_left = 0

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

print(s)

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

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

def step(queue_l, queue_r, c):
    if c == '(':
        queue_l += 1
    else:
        if queue_l > 0:
            queue_l -= 1
        else:
            queue_r += 1
    return (queue_l, queue_r)


out = []
queue_l = 0
queue_r = 0
for c in S:
    queue_l, queue_r = step(queue_l, queue_r, c)

print('(' * queue_r + S + ')' * queue_l)

Solution (Python):
import numpy as np

def d2():
    n = int(input())
    s = input()
    l = [ 1 if x=='(' else -1 for x in s[:] ]
    mt = np.cumsum(l) 
    mi = min(0, np.amin(mt))
    left = ''; right = ''
    if mi < 0:
        left = '('*(mi*-1)
    if mt[-1]-mi > 0:
        right = ')'*(mt[-1]-mi)
    
    print(left + s + right)

d2()

Solution (Python):
N = int(input())
data = list(input())
app = [0,0]
for i in range(N):
    if data[i] == ")":
        app[0] += 1
        if app[1] > 0:
            app[0] -= 1
            app[1] -= 1
    elif data[i] == "(":
        app[1] += 1
print("("*app[0] + "".join(data) + ")"*app[1])

Solution (Python):
import sys
import numpy as np
from math import *
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]
    input_raw = list((read_func().strip()))
    S = list(input_raw)
    left_count = 0
    for i in range(N):
        if input_raw[i] == '(':
            left_count += 1

        if input_raw[i] == ')':
            if left_count > 0:
                left_count -= 1
            else:
                S.insert(0, '(')

    for i in range(left_count):
        S.append(')')
    print "".join(S)



if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
data=list(map(lambda x:[str(x),-1],input()))
while 1:
    i=0
    while i<len(data):
        if data[i][0]==')' and data[i][1] == -1:
            break
        i+=1
    if i==len(data):
        break
    j=i-1
    while j>=0:
        if data[j][0]=='(' and data[j][1]==-1:
            data[i][1]=1
            data[j][1]=1
            break
        j-=1
    if j==-1:
        data[i][1]=1
        data.insert(0,['(',1])
while 1:
    i=len(data)-1
    while i>=0:
        if data[i][0]=='(' and data[i][1] == -1:
            break
        i-=1
    if i==-1:
        break
    data[i][1]=1
    data.append([')',1])
print(''.join(list(map(lambda x:x[0],data))))

Solution (Python):
N = int(raw_input())
S = raw_input()
S_sub = S
while ("()" in S):
    S = S.replace("()","")
a = 0
b = 0
for x in S:
    if x == ')':
        a += 1
    else:
        break
for x in S:
    if x == '(':
        b += 1
print "(" * a + S_sub + ")" * b

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

s=list(S)

i=0
j=0
while i<N and j<N:
    
    if s[i]=='(':
        j=i
        while j<N:
            
            if s[j]==')':
                s[i]='x'
                s[j]='x'
                
                i+=1
                break
            else:
                j+=1
    else:
        i+=1

op=s.count(')')
cl=s.count('(')

print '('*op+S+')'*cl

Solution (Python):

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

l = []
l.append(S)
i = 0
while True:
    if i > 1 and l[i] == l[i-1]:
        break
    l.append(l[i].replace("()",""))
    i += 1

a = l[i]
left = a.count(')')
right = a.count('(')
ans = '('*left + S + ')'*right
print(ans)

Solution (Python):
class Parenter:
    def __init__(self):
        self.left = 0
        self.right = 0
        self.data = ""

    def _run(self, letter):
        if letter == "(":
            self.data += "("
            self.left += 1
        if letter == ")":
            if self.left > 0:
                self.left -= 1
                self.data += ")"
            else:
                self.right += 1
                self.data += ")"
    
    def run(self, string):
        for s in string:
            self._run(s)
        self.data = "("*self.right + self.data + ")"*self.left
    

p = Parenter()
N = input()
data = input()
p.run(data)
print(p.data)

Solution (Python):
N = raw_input()
S = raw_input()

def insert(string):
    
    
    left = 0
    right = 0
    i=0
    while i < len(string):
        if string[i] == "(":
            left += 1
            
        else:
            right += 1
            
        if right > left:
            string = "(" + string
            left += 1
            
            i=0
            left = 0
            right = 0
        else:
            i += 1
    return string

def add_ket(string):
    bra = 0
    ket = 0
    for i in range(len(string)):
        if string[i] == "(":
            bra += 1
        else:
            ket += 1
    add = bra-ket
    string = string + add * ")"
    return string


tmp = insert(S)
print add_ket(tmp)

Solution (Python):
import numpy as np

N = int(input())
S = list(input())
S_v = np.array(S)
def pop(S):
    index=[]
    for i in range(len(S)-1):
        if S[i]=='('and S[i+1]==')':
            index.append(i)
            index.append(i+1)
    index = np.array(index)
    answer = np.delete(S,index)
    return answer
p = np.array([])
while len(S_v)!=len(p):
    p = S_v
    S_v = pop(S_v)

n_left = len(np.where(S_v==')')[0])
n_right = len(np.where(S_v=='(')[0])
print ('('*n_left+''.join(S)+')'*n_right)

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

opened = 0
min_opened = 0
for c in S:
    if c == '(' :
        opened += 1
    else:
        opened -= 1
        min_opened = min(opened, min_opened)

closed = 0
min_closed = 0
for c in S[::-1]:
    if c == ')' :
        closed += 1
    else:
        closed -= 1
        min_closed = min(closed, min_closed)

op = '(' * -min_opened if min_opened < 0 else ''
cl = ')' * -min_closed if min_closed < 0 else ''
print op + S + cl

Solution (Python):
if __name__ == '__main__':
    N = int(input())
    S = input()
    tmpS = S
    for i in range(50):
        tmpS = tmpS.replace("()", "")

    
    left_parenthesis_count = 0
    right_parenthesis_count = 0
    for moji in tmpS:
        if moji == "(":
            left_parenthesis_count += 1
        elif moji == ")":
            right_parenthesis_count += 1

    ans = S
    for i in range(right_parenthesis_count):
        ans = "(" + ans

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

    print(ans)

Solution (Python):
import copy

if __name__ == "__main__":

    N = int(input())
    s = input().replace("\n","")

    left = 0
    cp_s = copy.copy(s)
    for c in s:
        if c == "(":
            left += 1
        else:
            left -= 1
        if left < 0:
            cp_s = "(" + cp_s
            left += 1
    if left > 0:
        cp_s = cp_s + ")"*left
    print(cp_s)

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

def ans(S, cnt=0):
    H = []
    for i in S:
        if i == ")":
            if H:
                H.pop()
            else:
               cnt += 1
        else:
            H.append(1)
    return [cnt, len(H)]

L = ans(S)
A = "(" * L[0]
Z = ")" * L[1]

print(A + S + Z)

Solution (Python):


n = input()
s = raw_input()
cnt = 0
flg = 1
while(flg):
    for i in range(len(s)):
        if(s[i] == '('):
            cnt += 1
        elif(s[i] == ')'):
            cnt -= 1
            if(cnt<0):
                s = '('+s
                cnt = 0
                break
        if(i==len(s)-1):
            flg = 0
for i in range(cnt):
    s = s+')'
print(s)

Solution (Python):
import re

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

while True:
    pre = S
    S = re.sub(r'\(((L|R)*?)\)', r'L\1R', S)
    if pre == S:
        break

S = '(' * S.count(')') + S + ')' * S.count('(')
S = S.replace('L', '(')
S = S.replace('R', ')')
print(S)

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

leftAdd = 0
leftCount = 0
for i in range(N):
  if S[i]=='(':
    leftCount += 1
  elif leftCount == 0:
    leftAdd += 1
  else:
    leftCount -= 1

result = '(' * leftAdd + S + ')' * leftCount
print(result)

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

parentheses = list(input())

add_open = 0
close_buff = 0

result = ""

for elem in parentheses:
    result += elem

    if elem == "(":
        close_buff += 1

    elif elem == ")":
        if close_buff > 0:
            close_buff -= 1
        else:
            add_open += 1

print("("*add_open + result + ")"*close_buff)

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

while s.count("()") > 0:
    s = s.replace("()","")

left_count = s.count(")")
right_count = s.count("(")

for i in range(left_count):
    s_original = "(" + s_original
    
for i in range(right_count):
    s_original = s_original + ")"
    
print(s_original)

Solution (Python):
N = int(input())
S = input()
 
ans = []
st = 0
for c in S:
    if c == '(':
        st += 1
        ans.append('(')
    else:
        if st > 0:
            st -= 1
        else:
            ans.insert(0, '(')
        ans.append(')')
 
ans.extend(')' * st)
 
print(*ans, sep='')

Solution (Python):
N = int(input())
S = input().strip()
stack = []
l = 0
for i,c in enumerate(S):
  if c == ')':
    if stack:
      stack.pop()
    else:
      l += 1
  else:
    stack.append(i)
ans = '('*l + S + ')'*len(stack)
print(ans)

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

t = S

while S.count("()") != 0:
    S = S.replace("()", "")

L = S.count("(")
R = S.count(")")

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

Solution (Python):

def is_correct(s):
    l = 0
    for si in s:
        if si == "(": l += 1
        else: l -= 1
        if l < 0: return False
    return l == 0

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

flag = False
for i in xrange(105):
    for j in xrange(105):
        T = "("*i + S + ")"*j
        if is_correct(T):
            print T
            flag = True
            break
    if flag:
        break

Solution (Python):
n = int(input())
s = list(input())
stack = []


for v in s:
    if stack and stack[-1] == "(" and v == ")":
        stack.pop()
    else:
        stack.append(v)


for v in stack:
    if v == ")":
        s.insert(0, "(")
    else:
        s.append(")")

print("".join(s))

Solution (Python):


from copy import deepcopy
N = int(input())
S = input()
rawS = deepcopy(S)

while S.count("()"):
    S = S.replace("()", "")

right = S.count("(")
left = S.count(")")
print("("*left + rawS + ")"*right)

Solution (Python):
import sys

def main():
    n = int(sys.stdin.readline())
    s = sys.stdin.readline().rstrip()

    level = 0 
    left_paren_app_num = 0
    right_paren_app_num = 0

    
    

    for ch in s:
        if ch == '(':
            if level < 0:
                left_paren_app_num += - level
                level = 0
            level += 1
        elif ch == ')':
            level -= 1

    if level > 0:
            right_paren_app_num += level
            level = 0
    elif level < 0:
        left_paren_app_num += - level


    l_s = "".join(['(' for i in range(left_paren_app_num)])
    r_s = "".join([')' for i in range(right_paren_app_num)])
    print("%s%s%s" % (l_s, s, r_s))
    return 0

if __name__ == '__main__':
    sys.exit(main())

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

v1 = 0
v = 0
for s in S:
    if s == "(":
        v -= 1
    if s == ")":
        v += 1
    v1 = max(v1, v)

v2 = v1 + S.count("(") - S.count(")")

print "(" * v1 + S + ")" * v2

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

def get_purified(string):
    replaced = string.replace("()", "")
    if replaced == string:
        return replaced
    else:
        return get_purified(replaced)

purified_str = get_purified(S)
right_braces = purified_str.count("(")
left_braces = purified_str.count(")")
out = "(" * left_braces + S + ")" * right_braces
print(out)

Solution (Python):
n=int(raw_input())
s=raw_input()
cnt1=0
cnt2=0
for i in xrange(n):
    if s[i]=="(":
        cnt1+=1
    else:
        if cnt1>0:
            cnt1-=1
        else:
            cnt2+=1

for i in xrange(cnt1):
    s+=")"
for i in xrange(cnt2):
    s="("+s
print s

Solution (Python):
def makeinsert(s):
	left = 0
	inserttop = ''
	for i in range(0, len(s)):
		if s[i] == '(':
			left += 1
		else:
			if left > 0:
				left -= 1
			else:
				inserttop = '(' + inserttop
	insertbottom = ''
	for i in range(0, left):
		insertbottom = insertbottom + ')'
	return inserttop + s + insertbottom

raw_input()
s = raw_input()

print makeinsert(s)

Solution (Python):


import random
import sys

if __name__ == '__main__':
    def _(f):
        for l in f:
            for i in l.split():
                yield i

    g = _(sys.stdin)

    N, S = (int(next(g)),
                next(g),
    )

    SS = S

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

        while S.startswith(')'):
            S = S[1:]
            
            SS = '(' + SS

        while S.endswith('('):
            S = S[:-1]

            SS += ')'

    print(SS)

Solution (Python):


n = int(input())
s = input()
t0 = 0
t1 = 0
ans = s
for i in s:
    if i == '(' : t0 += 1
    if i == ')' : t1 += 1
    if t0 < 1 and t1 > 0:
        t1 -= 1
        ans = '(' + ans
    if t0 > 0 and t1 > 0:
        t0 -= 1
        t1 -= 1
print(ans + ')' * t0)

Solution (Python):
if __name__ == "__main__":
	N = int(input())
	S = input()
	left = []
	right = []
	for i,p in enumerate(S):
		if p == '(':
			left.append(i)
		else:
			if (len(left) > 0):
				left.pop(0)
			else:
				right.append(i)
	for x in range(len(right)):
		S = '(' + S
	for x in range(len(left)):
		S = S + ')'
	print (S)

Solution (Python):
N = int(input())
S = list(input())
r = 0
l = 0
for s in S:
	if s == "(":
		l += 1
	else:
		if l == 0:
			r += 1
		else:
			l -= 1
r2 = 0
l2 = 0
for s in S[::-1]:
	if s == ")":
		r2 += 1
	else:
		if r2 == 0:
			l2 += 1
		else:
			r2 -= 1
S = ["("] * r + S + [")"] * l
print("".join(S))

Solution (Python):


def main():
    n = int(raw_input())
    s = raw_input()

    total = 0
    prep = 0
    for c in s:
        if c == '(':
            total += 1
        else:
            total -= 1

        if total < 0:
            prep += 1
            total = 0

    print '(' * prep + s + ')' * total


main()

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

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(raw_input())
s=raw_input()
stack=[]
stidx=[]
ins=[]
for i in xrange(n):
    if s[i]=="(":
        stack.append(s[i])
        stidx.append(i)
    else:
        if len(stack)==0:
            ins.append(i)
        else:
            stack.pop()
            stidx.pop()
tmp=list(s)
for i in stidx:
    tmp[n-1]=tmp[n-1]+")"
for i in xrange(len(ins)):
    tmp[0]="("+tmp[0]
print "".join(tmp)

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

Solution (Python):


import sys
import os

N = int(input())
s = input().strip()
t = s

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

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

answer = '(' * right + s + ')' * left

print(answer)

Solution (Python):
n = raw_input()
s = raw_input()
stack = []
for l in s:
    stack.append(l)
    if stack[-2:] == ["(", ")"]:
        stack.pop()
        stack.pop()
for l in stack:
    if l == ")":
        s = "(" + s
    if l == "(":
        s += ")"

print s

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

a=0
b=0
c=0
for c in s:
    if c=='(':
        a+=1
    else:
        if a>0:
            a-=1
        else:
            b+=1

s+=')'*a
s = '('*b+s

print(s)