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())
s = list(input())
ans = "".join(s)

f = True
while f:
    f = False
    l = [True] * len(s)
    ns = []
    for i in range(len(s)-1):
        if (s[i] == "(") and (s[i + 1] == ")"):
            l[i], l[i + 1] = False, False
            f = True

    for i in range(len(s)):
        if l[i]:
            ns.append(s[i])

    s = ns.copy()

cnt = [0, 0]
for c in s:
    cnt[c == "("] += 1

print("(" * cnt[0] + ans + ")" * cnt[1])

Solution (Python):
n = input()
s = input()
count = 0
max_l = 0
max_r = 0

for c in s:
    if c =="(":
        count -= 1
    else:
        count += 1
    max_l = max(max_l, count)
count = 0
for c in s[::-1]:
    if c =="(":
        count += 1
    else:
        count -= 1
    max_r = max(max_r, count)

print("("*max_l + s + ")"*max_r)

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

right = 0
left = 0

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

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

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

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

if S == '(' or S == ')':
    print('()')
    exit()

l = []
cnt = 0
for i in range(N-1):
    if S[i] == '(':
        cnt += 1
        if S[i+1] == ')':
            l.append(['a', cnt])
            cnt = 0
        elif S[i+1] == '(' and i+1 == N-1:
            l.append(['a', cnt+1])
            cnt = 0
    elif S[i] == ')':
        cnt += 1
        if S[i+1] == '(':
            l.append(['b', cnt])
            cnt = 0
        elif S[i+1] == ')' and i+1 == N-1:
            l.append(['b', cnt+1])
            cnt = 0

if S[-1] != S[-2]:
    if S[-1] == '(':
        if l[-1][0] == 'a':
            l[-1][1] += 1
        else:
            l.append(['a', 1])
    elif S[-1] == ')':
        if l[-1][0] == 'b':
            l[-1][1] += 1
        else:
            l.append(['b', 1])


a = 0
b = 0
for i in range(len(l)):
    k, c = l[i]
    if k == 'a':
        q.append('('*c)
        a += c
    if k == 'b':
        q.append(')'*c)
        b += c
        if a < b:
            q.appendleft('('*(b-a))
            a += (b-a)
if a > b:
    q.append(')'*(a-b))

print(*q, sep='')

Solution (Python):
def abc064_d():
  _ = int(input())
  s = str(input())
  
  srev = s[::-1]
  
  op, cl = 0, 0
  
  f, r = '', ''
  for c in srev:
    if c == '(': op += 1
    else: cl += 1
    
    if op > cl:
      r += ')'
      cl += 1
  else:
    
    f += '(' * (cl - op)
  
  ans = f + s + r
  print(ans)

abc064_d()

Solution (Python):
n=int(input())
s=input()
cntl=0
for i in range(n-1,-1,-1):
    if s[i]==")":
        cntl+=1
    elif s[i]=="(" and cntl>0:
        cntl-=1
sl="("*cntl
cntr=0
for i in range(n):
    if s[i]=="(":
        cntr+=1
    elif s[i]==")" and cntr>0:
        cntr-=1
sr=")"*cntr
print(sl+s+sr)

Solution (Python):
n=int(input())
s=input()
ans=s
while len(s)>0:
  s=ans
  i=0
  while i<len(s):
    if s[i:i+2]=='()':
      s=(s[:i]+s[i+2:] if i!=0 else s[i+2:])
      i=-1
    i+=1
  l=s.count('(')
  r=s.count(')')
  if l>r :
    ans=ans+')'*(l-r)
  elif r>l:
    ans='('*(r-l)+ans
  elif len(s)>0:
    ans='('+ans
print(ans)

Solution (Python):
N=int(input())
A=input()
def check_l(A):
    for i in range(1,len(A)+1):
        if not i==len(A):
            if A[-i]=="(":
                pass
            else:
                return i
                break
        elif i==len(A):
            if A[-i]=="(":
                return 0
            else:
                return i
                break
def check_t(A):
    for i in range(0,len(A)):
        if not i==len(A)-1:
            if A[i]==")":
                pass
            else:
                return i
                break
        elif i==len(A)-1:
            if A[i]==")":
                a=len(A)
                return a
            else:
                return i
def all(A,C):
    if check_l(A)==0:
        for i in range(len(A)):
            C=C+")"
        print(C)
        exit()
    elif not check_l(A)==0:
        for i in range(check_l(A)-1):
            A=A+")"
            C=C+")"

    if check_t==len(A):
        for i in range(len(A)):
            C="("+C
        print(C)
        exit()
    else:
        for i in range(check_t(A)):
            A="("+A
            C="("+C

    for i in range(10**9):
        if "()" in A:
            A=A.replace("()","")
        else:
            break
    return A,C

X=A

for i in range(N):
    if A=="":
        print(X)
        break
    else:
        A,X=all(A,X)

Solution (Python):
n=int(input())
s=list(input())
over=0
left=0
right=0
center=""
for i in s:
    if over==0 and i==")":
        left+=1
    elif over!=0 and i==")":
        over-=1
    else:
        over+=1
    center+=i
right=over
print("("*left+center+")"*right)

Solution (Python):
import sys

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


def resolve():
    n = int(input())
    S = input()

    insert_L = 0
    cnt_L = 0

    for s in S:
        if s == '(':
            cnt_L += 1
        else:
            if cnt_L:
                cnt_L -= 1
            else:
                insert_L += 1

    insert_R = cnt_L

    res = '(' * insert_L + S + ')' * insert_R
    print(res)


if __name__ == '__main__':
    resolve()

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


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
s = input()
c = 0
d = 0
for i in range(n):
    if s[i] == '(':
        c += 1
    else:
        d += 1
used_c = [True]*n
used_d = [True]*n
for i in range(n):
    if s[i] == '(':
        for j in range(i+1, n):
            if s[j] == ')' and used_c[j]:
                c -= 1
                used_c[j] = False
                break
    else:
        for j in range(i):
            if s[j] == '(' and used_d[j]:
                d -= 1
                used_d[j] = False
                break
print('('*d+s+')'*c)

Solution (Python):
def main():
    from collections import deque

    N = int(input())
    s = input()

    ans = deque(s)
    cnt = 0
    for c in s:
        if c == ')':
            if cnt:
                cnt -= 1
            else:
                ans.appendleft('(')
        else:
            cnt += 1

    for _ in range(cnt):
        ans.append(')')

    print(''.join(ans))


if __name__ == '__main__':
    main()

Solution (Python):
N=int(input())
S=input()
n_left=0
n_right=0
for a in S:
    if a==")":
        if n_left==0:
            n_right+=1
        else:
            n_left-=1
    else:
        n_left+=1
print((n_right*"(")+S+(n_left*")"))

Solution (Python):
N = int(input())
S = list(input())
 
f = 0
b = 0
count = 0
for i in range(N - 1, -1, -1):
    if S[i] == '(':
        if count > 0:
            count -= 1
        else:
            b += 1
    else:
        count += 1
 
print('(' * count, end='')
print(*S, sep='', end='')
print(')' * b)

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

f = 0
b = 0
count = 0
for i in range(N - 1, -1, -1):
    if S[i] == '(':
        if count > 0:
            count -= 1
        else:
            b += 1
    else:
        count += 1
    
print ('(' * count, end = '')
print (*S, sep = '', end = '')
print (')' * b)

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

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

Solution (Python):
n = int(input())
s = list(input())
ans = ''
cnt = 0
for c in s:
    ans += c
    if c == ')':
        cnt -= 1
    else:
        cnt += 1
    if cnt < 0:
        ans = '(' + ans
        cnt = 0

cnt = 0
for c in s[::-1]:
    if c == ')':
        cnt += 1
    else:
        cnt -= 1
    if cnt < 0:
        ans += ')'
        cnt = 0

print(ans)

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

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

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

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

if L > R:
    S = S + (')' * (L - R))
if R > L:
    S = ('(' * (R - L)) + S

d = 0
mx = 0
for s in S:
    if s == ')':
        d += 1
    else:
        d -= 1
    mx = max(mx, d)

S = '(' * mx + S + ')' * mx
print(S)

Solution (Python):
N=int(input())
S=input()
ans1=0
maxans=0
def split(word): 
    return [char for char in word]  
def convert(s): 
  
    
    new = "" 
  
    
    for x in s: 
        new += x  
  
    
    return new 
for i in range(N):
  if S[i]=='(':
    ans1-=1
  else:
    ans1+=1
    if ans1>maxans:
      maxans=ans1
ans2=0
minans=0
for i in range(N):
  if S[N-1-i]==')':
    ans2-=1
  else:
    ans2+=1
    if ans2>minans:
      minans=ans2
r=split(S)
for i in range(minans):
  r.append(')')
r.reverse()
for i in range(maxans):
  r.append('(')
r.reverse()
print(convert(r))

Solution (Python):
N = int(input())
S = input().strip()
S1 = S
cur = 0
for i in range(len(S)):
    if S[i]=="(":
        cur += 1
    else:
        cur -= 1
    if cur<0:
        S1 = "("+S1
        cur += 1
S1 = S1+")"*cur
print(S1)

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

p=0
q=0
for i in s:
  if i=='(':
    p+=1
  else:
    if p>=1:
      p-=1
    else:
      q+=1
      p=0

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

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  





def n_fusoku(S, target='('):  
    stack = []
    ret = 0
    for s in S:
        if s == target:
            stack.append(s)
        else:
            if stack:
                stack.pop()
            else:
                ret += 1  
    return ret


N = read_a_int()
S = input()
n_kakko = n_fusoku(S)
n_kokka = n_fusoku(reversed(S), target=')')
print('(' * n_kakko + S + ')' * n_kokka)

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

max_k = 0
now = 0
for s in sl:
    if s == "(":
        now += 1
    else:
        now -= 1
    max_k = min(now, max_k)


print("(" * (-max_k) + "".join(sl) + max(now-max_k, 0) * ")")

Solution (Python):
n = int(input())
s = list(input())
l_ins = 0
l = 0
r = 0
for i in range(n):
    if s[i] == "(":
        l += 1
    else:
        r += 1
    l_ins = max(l_ins, r-l)
r_ins = 0
l = 0
r = 0
for i in range(n-1, -1, -1):
    if s[i] == "(":
        l += 1
    else:
        r += 1
    r_ins = max(r_ins, l-r)
ar = ["("]*l_ins + s + [")"]*r_ins
print("".join(ar))

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

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

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

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

Solution (Python):
from collections import deque


def main():
    n = int(input())
    s = input()
    left = 0
    stack = deque([])
    for ss in s:
        if ss == "(":
            stack.append("(")
        elif not stack:
            left += 1
        else:
            stack.pop()
    print(left * "(" + s + len(stack) * ")")


if __name__ == '__main__':
    main()

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

t = s
while "()" in t:
    t = t.replace("()", "")

a = t.count(")"); b = t.count("(")

print("(" * a + s + ")" * b)

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

need_left = 0
pointer = 0
for i in range(len(S)):
    if S[i] == '(':
        pointer += 1
    else:
        if pointer == 0:
            need_left += 1
        else:
            pointer -= 1
need_right = pointer

res = "(" * need_left + S + ")" * need_right
print(res)

Solution (Python):





























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


















co, cc = 0, 0
for ch in s:
    if ch == '(':
        co += 1
    if ch == ')':
        if co > 0:
            co -= 1
        else:
            cc += 1

ans = "(" * cc + "".join(s) + ")" * co
print(ans)

Solution (Python):
import sys
import math  
import bisect  
import queue  


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


def main():
    _ = int(input())
    S = input()

    T = []
    cnt = 0
    for s in S:
        if s == ')' and cnt == 0:
            T = ['('] + T + [')']
        elif s == ')' and cnt > 0:
            T = T + [')']
            cnt -= 1
        else:
            T = T + ['(']
            cnt += 1

    T = ['(' if t == ')' else ')' for t in T]
    new_S = T[::-1]

    T = []
    cnt = 0
    for s in new_S:
        if s == ')' and cnt == 0:
            T = ['('] + T + [')']
        elif s == ')' and cnt > 0:
            T = T + [')']
            cnt -= 1
        else:
            T = T + ['(']
            cnt += 1

    T = ['(' if t == ')' else ')' for t in T]
    T = T[::-1]
    print(''.join(T))


if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

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

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
s = input()
import copy
ss = copy.deepcopy(s)
import heapq

aa = []
bb = []
a,b,c = 0,0,0
for i in range(n):
    if s[i] == ")":
        c += 1
    
    if s[i] == "(":
        a += 1
        for j in range(i+1,n):
            if s[j] == ")":
                b += 1
                s = s[:j] + "-" + s[j+1:]
                break
            
ans = "("*c + ss + ")"*(a-b)
print(ans)

Solution (Python):
N = int(input())
S = input()
left = 0
right = 0
cnt1 = 0
for i in S:
    if i == '(':
        left += 1
    else:
        right += 1
    cnt1 = max(cnt1, right - left)
left = 0
right = 0
cnt2 = 0
for i in S[::-1]:
    if i == ')':
        left += 1
    else:
        right += 1
    cnt2 = max(cnt2, right - left)
ans = '(' * max(0, cnt1) + S + ')' * max(0, cnt2)
print(ans)

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

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

Solution (Python):
import sys


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


sys.setrecursionlimit(10 ** 9)


def main():
    N = int(input())
    S = list(input())
    answer = ""
    right = 0
    left = 0
    for s in S:
        if s == "(":
            if right > 0:
                answer = "(" * right + answer
                answer += ")" * right
                right = 0
            left += 1
            answer += "("
        else:
            if left > 0:
                answer += ")"
                left -= 1
            else:
                right += 1
    if left > 0:
        answer += ")" * left
    if right > 0:
        answer = "(" * right + answer + ")" * right
    print(answer)


if __name__ == "__main__":
    main()

Solution (Python):

import io
import math

data = int(input())
inin = input()

a1 = 0
a2 = 0

for i in range(data):
    if inin[i] == '(':
        a1 += 1
    else:
        if a1 > 0:
            a1 -= 1
        else:
            a2 += 1
print('('*a2+inin+')'*a1)

Solution (Python):
n = int(input())
s = list(input())
cnt = 0
for i in range(n-1, -1, -1):
    if s[i] == ')':
        cnt += 1
    elif cnt > 0:
        cnt -= 1
s = cnt*'(' + ''.join(s)
cnt = 0
for i in range(len(s)):
    if s[i] == '(':
        cnt += 1
    else:
        cnt -= 1       
print(s+')'*cnt)

Solution (Python):
from collections import deque
N = int(input())
S = list(input())
T = deque(S[:])
ins = []
pointer = 0
a = 0
for i in range(N):
  if S[i] == ')':
    if pointer >= 1:
      pointer -= 1
    else:
      T.appendleft('(')
  else:
    pointer += 1
  
a = 0
b = 0
for t in T:
  if t == ')':
    b += 1
  else:
    a += 1

for i in range(max(a-b, 0)):
  T.append(')')
print(''.join(T))

Solution (Python):


N = int(input())
s = input()
l = []
AB = []
for i in range(N):
    l.append(s[i])
    if(s[i] == '('):
        AB.append('A')
    else:
        AB.append('B')



first_A_lack_counter = 0
last_B_lack_counter = 0

mode = 'even' 


index = 0
while True:
    
    
    if(mode == 'even'):
        if(AB[index] == 'A'):
            mode = 'B_lack'
            last_B_lack_counter += 1
            
        elif(AB[index] == 'B'):
            mode = 'A_lack'
            first_A_lack_counter += 1
            
    elif(mode == 'A_lack'):
        if(AB[index] == 'A'):
            mode = 'B_lack'
            last_B_lack_counter = 1
            
        elif(AB[index] == 'B'):
            first_A_lack_counter += 1
            
    elif(mode == 'B_lack'):
        if(AB[index] == 'A'):
            last_B_lack_counter+= 1
            
        elif(AB[index] == 'B'):
            last_B_lack_counter -= 1
            
        if(last_B_lack_counter == 0):
            mode = 'even'
            
    
    index += 1
    if(index == N):
        break







first_A = []
for i in range(first_A_lack_counter):
    first_A.append('(')
l = first_A + l

for i in range(last_B_lack_counter):
    l.append(')')


print('{}'.format(''.join(l)))

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007



def main():
	n = int(input())
	
	s = input()
	rc=0
	rc_max=0
	for c in s:
		if c == ')':
			rc+=1
			rc_max=max(rc_max, rc)
		else:
			rc -= 1
	
	lc=0
	lc_max=0
	for c in s[::-1]:
		if c == '(':
			lc += 1
			lc_max=max(lc, lc_max)
		else:
			lc -= 1
	ret = '(' * rc_max + s + ')'*lc_max
	print(ret)
			
	
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
n=int(input());s=input()
ans = '';v = 0;vmin = 0
for s0 in s:
    if s0 == '(':
        v += 1
    else:
        v -= 1
        vmin = min(v,vmin)
left = '('; right = ')'
if vmin < 0:
    ans += left*(-1*vmin)
    v += (-1*vmin)
if v == 0:
    ans += s
elif v > 0:
    ans += s + right*v
else:
    ans += left*(-1*v) + s
print(ans)

Solution (Python):
N=int(input())
S=input().rstrip()
t=""
d=0
for i in range(N):
  if S[i]=="(":
    d+=1
    t+="("
  else:
    if d>0:
      t+=")"
      d-=1
    else:
      t="("+t+")"
if d>0: t+=")"*d
else: t="("*(-d)+t
print(t)

Solution (Python):
N = int(input())
S = input()
hidari = 0
migi = 0
for i in range(N):
  if S[i] == '(':
    hidari += 1
  else:
    if hidari > 0:
      hidari -= 1
    else:
      migi += 1
S = '(' * migi + S + ')' * hidari
print(S)

Solution (Python):
n=int(input())
kakko=[1 if i == '(' else -1 for i in list(input())]
tmp=0
x=0
y=0
for i in range(n):
    x+=kakko[i]
    if tmp<abs(x) and x<0:
        tmp+=1
kakko=[1]*tmp+kakko

if sum(kakko)>0:
    tmp=sum(kakko)
    kakko=kakko+[-1]*tmp
ans=['(' if i==1 else ')' for i in kakko]
print(''.join(ans))

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

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

Solution (Python):
n = int(input())
s = list(input())
leng = []
cnt = 1
for i in range(n-1):
    if s[i] == s[i+1]:
        cnt += 1
    else:
        leng.append([s[i], cnt])
        cnt = 1
if s[-1] == "(":
    leng.append(["(", cnt])
else:
    leng.append([")", cnt])
if s[0] == ")":
    leng.insert(0,["(", leng[0][1]])
if s[-1] == "(":
    leng.insert(len(leng),[")", leng[-1][1]])

leng2 = []
for i in range(0, len(leng), 2):
    l = leng[i]
    r = leng[i+1]
    if l[1] == r[1]:
        pass
    elif l[1] < r[1]:
        leng2.append([")",r[1]-l[1]])
    else:
        leng2.append(["(", l[1]-r[1]])

lc = 0
rc = 0
for i in range(len(leng2)):
    if leng2[i][0] == "(":
        lc += leng2[i][1]
    else:
        rc += leng2[i][1]
    if rc - lc > 0:
        leng[0][1] += rc-lc
        lc = 0
        rc = 0
leng[-1][1] += lc-rc

ans = []
for i in range(len(leng)):
    tar = leng[i]
    for j in range(tar[1]):
        ans.append(tar[0])
print("".join(ans))

Solution (Python):
from collections import defaultdict
n = int(input())
s = input()
ans = ""
cnt1=cnt2=cnt3=0
tmp = ""
for i in s:
    if i==")":

        if cnt2==0:
            cnt1+=1
            tmp+="("
            ans+=")"
        if cnt2>0:
            cnt2-=1
            ans+=")"

    if i=="(":
        cnt1=0
        cnt2+=1
        ans+="("
        if len(tmp)>0:
            ans = tmp+ans
            tmp=""

if cnt1>0:
    ans = "("*cnt1+ans
if cnt2>0:
    ans += ")"*cnt2
print(ans)

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

l = S.count('(')
r = S.count(')')
d = r - l

if d > 0:
    S = '(' * d + S
if d < 0:
    S = S + ')' * (-d)

l, r, d = 0, 0, 0
for s in S:
    if s == '(':
        l += 1
    if s == ')':
        r += 1
    d = max(d, r - l)

if d > 0:
    S = '(' * d + S + ')' * d

print(S)

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

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

while True:
    check = 0
    for i in range(len(s)):
        if s[i] == "(":
            check += 1
        else:
            check -= 1
            
        if check < 0:
            s.insert(0, "(")
            break
    else:
        for _ in range(check):
            s.append(")")
        print("".join(s))
        break

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

Solution (Python):
n = int(input())
S = input()
T = S
for i in range(100):
    for j in range(n):
        if j+1 < len(S) and S[j] == '(' and S[j+1] == ')':
            S = S[:j]+S[j+2:]
a = S.count('(')
b = S.count(')')
print('('*b+T+')'*a)

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

ret_left = 0

left = 0
for s in S:
    if s == ")":
        if left == 0:
            ret_left += 1
        else:
            left -= 1
    else:
        left += 1
        
ret_right = left

for i in range(ret_left):
    print("(", end = "")
print(S, end = "")
for i in range(ret_right):
    print(")", end = "")

Solution (Python):
def main():
    N = int(input())
    S = input()
    le, ri = 0, 0
    addle, addri = 0, 0
    for s in S:
        if s == ")":
            le += 1
            if le <= ri:
                le -= 1
                ri -= 1
            else:
                le -= 1
                addri += 1
        elif s == "(":
            ri += 1
    addle = ri
    print("("*addri + S + ")"*addle)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    S = input().strip("\n")
    havePair = [False] * N
    rightN = 0
    leftLeft = 0
    ri = deque()
    for i in range(N):
        if S[i] == "(": 
            rightN += 1
            ri.append(i)
        else:
            if ri:
                rmin = ri.popleft()
                rightN -= 1
            else: leftLeft += 1

    Ans = ["(" * leftLeft, S, ")" * rightN]
    print("".join(Ans))
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
N = int(input())
S = input()
op = 0
for c in S:
    if c=='(':
        op += 1
    elif op > 0:
        op -= 1
cl = 0
for c in S[::-1]:
    if c==')':
        cl += 1
    elif cl > 0:
        cl -= 1

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

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

ans = s
ans = list(ans)

cum = 0
for i in range(n):
    if s[i] == '(':
        cum += 1
    else:
        cum -= 1
    if cum < 0:
        ans = ['('] + ans
        cum = 0
else:
    ans = ans + [')']*cum

print(''.join(ans))

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

level = [0] * (N + 1)
level_tmp = 0
for i in range(N):
    level_tmp += (1 if S[i] == '(' else -1)
    level[i + 1] = level_tmp



left = '(' * max(0, -1 * min(level))
right = ')' * max(0, level[-1] + max(0, -1 * min(level)))

print(left + S + right)

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

    left = 0
    right = 0
    for c in s:
        if c == '(':
            right += 1
        else:
            if right > 0:
                right -= 1
            else:
                left += 1

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

if __name__ == '__main__':
    main()

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

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

def solve():
    i = 0
    opens = []
    inspos = 0
    while i < len(S):
        if S[i] == '(':
            opens.append(i)
        elif opens:
            opens.pop()
        else:
            S.insert(inspos, '(')
            i += 1
        i += 1
    for _ in range(len(opens)):
        S.append(')')

solve()
print(''.join(S))

Solution (Python):
n = int(input())
s = input()
l = 0
r = 0
count = 0
need = 0
for i in range(n):
    if s[i] == "(":
        l += 1
        count += 1
    else:
        r += 1
        if count > 0:
            count -= 1
        else:
            need += 1
print("(" * need + s + ")" * (l + need - r))

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

left_num = 0
right_num = 0

for i in range(N):
    if S[i] == '(':
        right_num += 1
    else:
        if right_num > 0:
            right_num -= 1
        else:
            left_num += 1

ans = '('*left_num + S + ')'*right_num
print(ans)

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

s =str(input())


left_save = 0
dept=0

for i in range(len(s)):
    if s[i] ==')':
        if left_save == 0:
            dept +=1
        else:
            left_save-=1
            
    else:
        left_save+=1

ans = '('*dept + s + ')'*left_save

print(ans)

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

Solution (Python):
if __name__ == '__main__':
    n = int(input())
    s = list(input())
    right_parentheses = 0
    needed_right_parentheses = 0
    for i in s:
        if i == '(':
            right_parentheses += 1
        else:
            if right_parentheses > 0:
                right_parentheses -= 1
            else:
                needed_right_parentheses += 1

    ans = ['('] * needed_right_parentheses + s + [')'] * right_parentheses
    print(''.join(ans))

Solution (Python):
N = int(input())
S = input()
a = '('
b = ')'

i = 0
cntA = 0
ans = S
for s in S:
    if s == a:
        cntA += 1
    else:
        if cntA == 0:
            ans = '(' + ans
        else:
            cntA -= 1
else:
    ans = ans + ')' * cntA

print(ans)

Solution (Python):
from collections import deque
def main():
    n = int(input())
    s = list(input())

    stack = []
    ans = deque([])
    for c in s:
        if c == '(':
            ans.append('(')
            stack.append('(')
        
        if c == ')':
            if stack==[]:
                ans.appendleft('(')
                ans.append(')')
            else:
                stack.pop()
                ans.append(')')
    for c in stack:
        ans.append(')')

    for c in ans:
        print(c,end="")
    print()

if __name__ == "__main__":
    main()

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

left = 0
right = 0

for i in range(N):
    if right == 0 and S[i] == ')':
        left += 1
    elif S[i] == '(':
        right += 1
    elif right > 0 and S[i] == ")":
        right -= 1
        
print("("*left + S + ")"*right)