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 = str(input())

ans_s = s
ans_head = 0
ans_tail = 0

def remove(s):
    while True:
        if len(s) <= 0:
            break
        pre_len = len(s)
        s = s.replace("()", "")
        if len(s) == pre_len:
            break
    return s

s = remove(s)
while len(s) > 0:
    s = remove(s)
    if s[0] == ')':
        ans_head += 1
        s = remove('(' + s)
    else:
        ans_tail += 1
        s = remove(s + ')')
    
print('('*ans_head + ans_s + ')' * ans_tail)

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

open_left=0
open_right=0
for c in S:
    if c == ')':
        if open_left > 0:
            open_left -= 1
        else:
            open_right += 1
    else:
        open_left += 1


ans = '('*open_right + S + ')' * open_left
print(ans)

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):
from collections import deque
n = int(input())
s = input()

stack = []
que = deque()
for i in range(n):
    t = s[i]
    if t == '(':
        que.append('(')
        stack.append('(')
    else: 
        if stack and stack[-1] == '(':
            stack.pop()
            que.append(')')
        else:
            que.appendleft('(')
            que.append(')')
            

ans = ''.join(que) + ')' * len(stack)
print(ans)

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
n = int(input()) 

s = list(input())
que = deque()
stack = []

for i in range(n):
    t = s[i]
    if t == '(':
        stack.append(t)
        que.append(t)
    else: 
        if stack:
            if stack[-1] == '(':
                stack.pop()
                que.append(')')
            else:
                stack.append(')')
        else:
            que.appendleft('(')
            que.append(')')

print(''.join(que) + ')' * len(stack))

Solution (Python):
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]



N = ii()
S = input()

pos = 0
r_cnt = 0

while pos < N and S[pos]==')':
    r_cnt += 1
    pos += 1

l_cnt = 0

for i in range(pos, N):
    if S[i]=='(':
        l_cnt += 1
    else:
        if l_cnt==0:
            r_cnt += 1
        else:
            l_cnt -= 1


print('('*r_cnt + S + ')'*l_cnt)

Solution (Python):



def main():
    n = int(input())
    s = input()
    count = 0
    new_left = 0
    new_right = 0

    
    
    for si in s:
        if si == '(':
            count += 1
        else:
            count -= 1

            if count == -1:
                count = 0
                new_left += 1

    new_right = count

    print('(' * new_left + s + ')' * new_right)


if __name__ == '__main__':
    main()

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

Solution (Python):
n=int(input())
s=input()
from itertools import groupby as gb
head=0
m=0
for k,v in [(a,len(list(b))) for a,b in gb(s)]:
    if k==")":
        if m<v:head+=v-m;m=0
        else:m-=v
    else:
        m+=v
print("("*head+s+")"*m)

Solution (Python):
n = int(input())
p,cr,cl = 0,0,0
c = 0 
s  = input()
for i in list(s):
    if i =="(":
        p+=1
        cl +=1
    else:
        cr+=1
        if p>0:
            p-=1
            c+=1


print("("*(cr-c) + s + ")"*(cl-c)  )

Solution (Python):
n = int(input())
array = list(input())
ret = []

count = 0
for str in array:
    if str == "(":
        count += 1

    if str == ")":
        count -= 1
        if count < 0:
            for i in range(-count):
                ret.insert(0, "(")
            count = 0
    ret.append(str)
for i in range(count):
    ret.append(")")

print(''.join(ret))

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

plus = 0
minus = 0

for i in range(n):
    if s[i] == '(':
        plus += 1
    else:
        plus -= 1
        if plus < 0:
            minus += 1
        plus = max(plus,0)
        
print('('*minus+s+')'*plus)

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

left = 0
right = 0
tmp = 0
tmp_li = []

if s[0] == '(':
    bfr = 0
    tmp = 1
else:
    bfr = 1
    tmp = -1



for i in range(1,n):
    if bfr == 0:
        if s[i] == '(':
            
            tmp += 1
        else:
            
            tmp_li.append(tmp)
            tmp = -1
            bfr = 1
    else:
        if s[i] == '(':
            
            tmp_li.append(tmp)
            tmp = 1
            bfr = 0
        else:
            tmp -= 1

tmp_li.append(tmp)


tmp2_li = []
tmp = 0

for i in range(len(tmp_li)):
    tmp += tmp_li[i]
    if tmp < 0:
        tmp2_li.append(tmp)
        tmp = 0

tmp2_li.append(tmp)

minus = 0
plus = 0

for i in range(len(tmp2_li)):
    if tmp2_li[i] < 0:
        minus += tmp2_li[i]
    else:
        plus += tmp2_li[i]
        


print('('*(-minus)+s+')'*plus)

Solution (Python):


def submit():
    n = int(input())
    s = input()

    cnt = 0
    op = 0
    for c in s:
        if c == "(":
            cnt += 1
        else:
            if cnt == 0:
                op += 1
            else:
                cnt -= 1

    print("(" * op + s + ")" * cnt)


submit()

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

d = [0] * n
nl = 0
nr = 0
for i in range(n):
    if S[i] == '(': nl += 1
    if S[i] == ')': nr += 1
    d[i] = nl - nr

d = [0] + d
x = -min(d)



print('('*x + S + ')'*(d[-1]+x))

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

Solution (Python):
n=int(input())
s=list(input().strip())
l=[]
for i in s:
    if l!=[]:
        if l[-1]=='(' and i==')':
            l.pop()
        else:
            l.append(i)
    else:
        l.append(i)
cntl=l.count(')')
cntr=l.count('(')
ans='('*cntl+''.join(s)+')'*cntr
print(ans)

Solution (Python):
n = int(input())
s = input()
need_L = 0
cnt = 0
for c in s:
    if c == ')':
        cnt += 1
        if 0 < cnt:
            need_L += 1
            cnt -= 1
    elif c == '(':
        cnt -= 1
need_R = max(-cnt, 0)
print('('*need_L + s+')'*need_R)

Solution (Python):
N = int(input())
S = input()
d = '111'
ans = S
d


a = 0

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

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

Solution (Python):


def main():
    n = int(input())
    s = input()
    x = 0
    xmin = 0
    for c in s:
        x += (1 if c == "(" else -1)
        xmin = min(xmin, x)
    l = max(-xmin, 0)
    r = x + l
    print("(" * l + s + ")" * r)

if __name__ == "__main__":
    main()

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

rcount = 0
rmargin = 0
lcount = 0
lmargin = 0
for i in range(n):
    if s[i] == ')':
        if rmargin ==0: rcount +=1
        else: rmargin -= 1
    else: rmargin +=1

    if s[-1-i] == '(':
        if lmargin ==0: lcount +=1
        else: lmargin -= 1
    else: lmargin +=1

ans = '('*rcount + s + ')'*lcount
print(ans)

Solution (Python):
from collections import deque

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

res = deque()
pcnt = 0
for s in S:
    if s == '(':
        pcnt += 1
    else:
        if pcnt:
            pcnt -= 1
        else:
            res.appendleft('(')
    res.append(s)
if pcnt:
    res.append(')' * pcnt)
print(*res, sep='')

Solution (Python):
n,s,sj=int(input()),input(),''.join
l=sum([1 if c==')' else 0 for c in s])
r=n-l
t=s[:]
while True:
    for i in range(len(t)-1):
        if t[i:i+2]=='()':
            t,l,r=t[:i]+t[i+2:],l-1,r-1
            break
    else:break
print(sj(['(']*l)+s+sj([')']*r))

Solution (Python):
n = int(input())
s= input()
lc = sum([1 if c==')' else 0 for c in s])
rc = n-lc
ss = s[:]
while True:
    for i in range(len(ss)-1):
        if ss[i:i+2] == '()':
            ss=ss[:i] + ss[i+2:]
            lc,rc = lc-1,rc-1
            break
    else:
        break
news = ''.join(['(' for _ in range(lc)]) + s + ''.join([')' for _ in range(rc)])
print(news)

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

count = 0
left = 0
right = 0

for i in s:
    if i == '(':
        count += 1
    else:
        count -= 1

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

right = count

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

Solution (Python):
input()
s = input()
ans = ''
cnt_l = 0
cnt_r = 0
cur = 0
for c in s:
    if c == '(':
        if cur < 0:
            cnt_l += abs(cur)
            cur = 0
        cur += 1
    else:
        cur -= 1
if cur > 0:
    cnt_r += cur
else:
    cnt_l += abs(cur)
print(cnt_l*'(' + s + cnt_r*')')

Solution (Python):
n=int(input())
s=input()
a=0 
b=0 
cnt=0
for i in range(n):
    if s[i]=="(":
        if a<b:
            cnt+=b-a
            a,b=1,0
        else:
            a+=1
    else:
        b+=1
if a<b:
    cnt+=b-a
s=(cnt*"("+s)
a=s.count("(")
b=len(s)-a
print(s+")"*(a-b))

Solution (Python):
def main():
    from collections import deque
    n = int(input())
    s = input()
    need_left, need_right = 0, 0
    for i in s:
        if i == "(":
            need_right += 1
        else:
            if need_right == 0:
                need_left += 1
            else:
                need_right -= 1
    for i in range(need_left):
        s = "(" + s
    for j in range(need_right):
        s = s + ")"
    print(s)
if __name__ == "__main__":
    main()

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

flag = True

ans = []

count = 0

for i in s:
    if flag:
        if i==')':
            ans.append(')')
            ans.insert(0, '(')
        else:
            flag = False
            ans.append('(')
            count += 1
    else:
        if i=='(':
            count += 1
            ans.append('(')
        else:
            ans.append(')')
            count -= 1
            if count == 0:
                flag = True
                
for j in range(count):
    ans.append(')')

print(''.join(map(str,ans)))

Solution (Python):
n = int(input())
array = list(input())
ret = []

count = 0
for str in array:
    if str == "(":
        count += 1

    if str == ")":
        count -= 1
        if count < 0:
            for i in range(-count):
                ret.insert(0, "(")
            count = 0
    ret.append(str)
for i in range(count):
    ret.append(")")

print(''.join(ret))

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

ans = ""

l = 0
r = 0

for i in range(N):
    if S[i] == "(":
        l += 1
        ans += "("
    else:
        r += 1
        if l >= r:
            ans += ")"
        else:
            ans = "(" + ans + ")"
            l += 1

while l < r:
    ans = "(" + ans
    l += 1
while l > r:
    ans += ")"
    r += 1

print(ans)

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

Solution (Python):
def solve():
    N = int(input())
    S = input()
    
    stack = 0
    ans = ""
    for i in range(N):
        if S[i] == '(':
            stack += 1
            ans += S[i]
        else:
            ans += S[i]
            if stack == 0:
                ans = '(' + ans
            else:
                stack -= 1
    else:
        if stack != 0:
            ans += ')' * stack
    
    print(ans)


    
if __name__ == '__main__':
    solve()

Solution (Python):
def solve():
    N = int(input())
    S = input()
    add = ""
    left = 0
    right = 0
    for i in range(N):
        if S[i] == '(':
            left += 1

        else:
            right += 1
            if left < right:
                left += 1
                add += '('

    add2 = ""

    left = 0
    right = 0
    for i in range(N-1,-1,-1):
        if S[i] == '(':
            left += 1
            if left > right:
                right += 1
                add2 += ')'

        else:
            right += 1
    print(add+S+add2)

    
if __name__ == '__main__':
    solve()

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


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


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


def print_matrix(mat):
    for i in range(len(mat)):
        print(*mat[i])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False



def test1(s):
    stack = deque()
    out = ''
    tmp = ''

    for i in range(len(s)):
        if s[i] == ')' and len(stack) == 1 and stack[-1] == '(':
            out += '(' + tmp + ')'
            tmp = ''
            stack.pop()
        elif s[i] == ')' and len(stack) > 0 and stack[-1] == '(':
            tmp = '(' + tmp + ')'
            stack.pop()
        elif s[i] == ')' and len(stack) == 0:
            tmp = '(' + tmp + ')'
        else:
            stack.append('(')
            out += tmp
            tmp = ''

    for i in range(len(tmp)//2):
        out = '(' + out + ')'

    tmp = ''
    while len(stack) > 0:
        tmp = '(' + tmp + ')'
        stack.pop()

    out += tmp

    return out


def test2(s):
    stack = deque()
    out = ''
    tmp = ''

    for i in range(len(s)):
        if s[i] == ')' and len(stack) > 0 and stack[-1] == '(':
            tmp = '(' + tmp + ')'
            stack.pop()
        elif s[i] == ')' and len(stack) == 0:
            tmp = '(' + tmp + ')'
        else:
            stack.append('(')
            out += tmp
            tmp = ''
        
        

    out += tmp

    tmp = ''
    while len(stack) > 0:
        tmp = '(' + tmp + ')'
        stack.pop()

    out += tmp

    return out


def main():
    N = I()
    s = S()
    c = 0
    stack = deque()

    for i in range(len(s)):
        if s[i] == '(':
            stack.append('(')
            c += 1
        elif len(stack) > 0:
            stack.pop()
            c -= 1
        else:
            c += 1

    
    print('(' * (c - len(stack)) + s + ')' * len(stack))

    
    

    


if __name__ == '__main__':
    main()

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

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


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

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

Solution (Python):

import math
import heapq
import bisect
import numpy as np
from collections import Counter, deque


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

x = 0
d = 0
for s in S:
    if s == '(': d += 1
    else: d -= 1

    x = min(x,d)

ans = '('*(-x) + S + ')'*(d-x)
print(ans)

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

def one(X):
  L, R = 0, 0
  for x in X:
    if x == "(":
      R += 1
    else:
      if R == 0:
        L += 1
      else:
        R -= 1
  return L*"("+X+R*")"

def two(X):
  mL = 0
  for i in X:
    if i == ")":
      mL += 1
    else:
      break
  mR = 0
  for i in X[::-1]:
    if i == "(":
      mR += 1
    else:
      break
  X = mL * "(" + X + mR * ")"
  L = len([i for i in X if i == ")"])
  R = len(X) - L
  if L > R:
    X = (L - R) * "(" + X
  else:
    X += (R - L) * ")"
  return X







print(one(X))

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

Solution (Python):
from collections import deque


def solve():
    N = int(input())
    S = input()
    ans = deque(S)
    
    l, r = 0, 0
    for i in range(N):
        if S[i] == '(':
            l += 1
        else:
            if 0 < l:
                l -= 1
            else:
                r += 1
    
    for _ in range(l):
        ans.append(')')
    for _ in range(r):
        ans.appendleft('(')
    print(''.join(ans))


if __name__ == '__main__':
    solve()

Solution (Python):

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

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

Solution (Python):

import math
import itertools
import statistics

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

amari = 0
plus = 0

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

for i in range(amari):
    print("(", end="")

print(s, end="")

for i in range(plus):
    print(")", end="")

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

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

stk = []
for s in S:
    if len(stk) == 0 or stk[-1] == ')' or s == '(':
        stk.append(s)
    else:
        stk.pop()

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

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

let = 0
let2 = ""
for i in range(n):
	if s[i] == "(":
		let += 1
	else:
		if let > 0:
			let -= 1
		else:
			let2 += "("
print (let2 + s + ")"*let)

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

result = S
while True:
    while True:
        t = S.replace('()', '')
        if t == S:
            break
        S = t
    if S == '':
        break
    elif S[0] == ')':
        S = '(' + S
        result = '(' + result
    elif S[0] == '(':
        S = S + ')'
        result = result + ')'
print(result)

Solution (Python):
n = int(input())
s = input()
l = 0
r = 0
for i in s:
    if i == ")":
        if r == 0:
            l += 1
            
        else:
            r -= 1
    else:
        r += 1

print("("*l+s+")"*r)

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

a=0
l=0

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

print('('*l+s+')'*a)

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

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

ans = "(" * top + S + ")" * temp
print(ans)

Solution (Python):
n = int(input())
s = str(input())
A = [0]
cum = 0
ans = ''
for i in range(n):
    if s[i] == '(':
        cum += 1
    else:
        cum -= 1
    if cum == -1:
        ans = '('+ans
        ans += s[i]
        cum = 0
    else:
        ans += s[i]
else:
    if cum > 0:
        ans += ')'*cum
print(ans)

Solution (Python):
n = int(input())
s = str(input())
A = [0]
cum = 0
ans = ''
for i in range(n):
    if s[i] == '(':
        cum += 1
    else:
        cum -= 1
    if cum == -1:
        ans = '('+ans
        ans += s[i]
        cum = 0
    else:
        ans += s[i]
else:
    if cum > 0:
        ans += ')'*cum
print(ans)

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

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
S = input()
ans = []
r = 0
l = 0
for s in S:
    if s == "(":
        r += 1
    else:
        if r >= 1:
            
            r -= 1
        else:
            l += 1
print(l * "(" + S + r * ")")

Solution (Python):
from collections import deque

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

d = deque()
o = deque()
stack = []
for i in range(N):
    if S[i] == '(':
        stack.append(S[i])
        d.append('(')
    else:
        if len(stack) > 0:
            if stack[-1] == '(':
                stack.pop()
                d.append(')')
                
            else:
                stack.append(')')
        else:
            d.appendleft('(')
            d.append(')')

print(''.join(d) + ''.join([')']*len(stack)))

Solution (Python):
n = int(input())
s = input()
a = 0
b = 0

for c in s:
  if c == '(':
    a += 1
  elif c == ')' and a != 0:
    a -= 1
  else:
    b += 1
    
s = ('('*b) + s + (')'*a)

print(s)

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

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

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

tyo=0
tmax=0
for i in range(n):
  if s[i]==")":
    tyo+=1
    tmax=max(tmax,tyo)
  else:  
    tyo-=1

lastkcnt=tmax+s.count("(")-s.count(")")
ans="("*tmax+s+")"*lastkcnt
print(ans)

Solution (Python):
n = int(input())
s = list(input())
m = 0
l = 0
for i in range(n):
    if s[i] == ")":
        m += 1
    else:
        m -= 1
    if l < m:
        l = m
s1 = ["("] * l
for i in s:
    if i == "(":
        l += 1
    else:
        l -= 1
s2 = [")"] * l
s = s1 + s + s2
print("".join(s))

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

A = list(input())

B = []
t = 0
for i in A:
    if i == "(":
        B.append(i)
        t += 1
    else:
        if t == 0:
            B = ["("] + B
            B.append(")")
        else:
            B.append(i)
            t -= 1
for i in range(t):
    B.append(")")
print("".join(B))

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

ans = deque(s)
cnt = 0
for i in range(n):
    if s[i] == ')':
        if cnt == 0:
            ans.appendleft('(')
        else:
            cnt -= 1
    else:
        cnt += 1

s.reverse()
cnt = 0
for i in range(n):
    if s[i] == '(':
        if cnt == 0:
            ans.append(')')
        else:
            cnt -= 1
    else:
        cnt += 1

print(''.join(ans))

Solution (Python):
n=int(input())
kakko=input()
openk=0
closek=0
for i in range(n):
    if kakko[i]=="(":
        openk+=1
    else:
        if openk>0:
            openk-=1
        else:
            closek+=1
mae="("*closek
ushiro=")"*openk
ans=mae+kakko+ushiro
print(ans)

Solution (Python):
from itertools import groupby
N = int(input())
S = input()
ans = []

a=0
a1=0
b=0
b1=0
S1 = groupby(list(S))
for key,group in S1:
  group = list(group)
  if list(key)==['(']:
    a1+=len(group)
  else:
    if a1<=len(group):
      b1+=len(group)-a1
      a1 = 0
    else:
      a1 -=len(group)
S = S+")"*a1
S = "("*b1+S
print(S)

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

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

add_left = 0
add_right = 0
for c in S:
    if c == '(':
        add_right += 1
    elif add_right == 0:
        add_left += 1
    else:
        add_right -= 1
ans = '(' * add_left + S + ')' * add_right
print(ans)

Solution (Python):
n = int(input())
s = input()
n = len(s)
l = 0
r = 0
tmp = 0
for i in range(n):
  if(s[n-1-i] == ')'):
    tmp += 1
  else:
    tmp -= 1
    if(tmp < 0):
      tmp = 0
      r += 1
tmp = 0
for i in range(n):
  if(s[i] == '('):
    tmp += 1
  else:
    tmp -= 1
    if(tmp < 0):
      tmp = 0
      l += 1


for i in range(l):
  print('(',end = '')
print(s,end='')
for i in range(r):
  print(')',end = '')

Solution (Python):

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

forward, backward = 0, 0
v = 0
for i in range(N):
    if S[i] == '(':
        v += 1

    else:
        v -= 1

    if v < 0:
        forward += 1
        v = 0

if v > 0:
    backward = v

ret = '(' * forward + S + ')' * backward
print(ret)

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

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

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

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():
    q = deque()
    N = I()
    s = S()
    cnt_l = 0 
    cnt_r = 0 

    for c in s:
        if c == '(':
            cnt_l += 1
        else:
            cnt_r += 1
            if cnt_l > 0:
                cnt_l -= 1
                cnt_r -= 1
        q.append(c)
    while cnt_l:
        q.append(')')
        cnt_l -= 1
    while cnt_r:
        q.appendleft('(')
        cnt_r -= 1
    ans = []
    for c in q:
        ans.append(c)
    print(''.join(ans))

main()

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

stack = ""

for e in s:
	stack += e
	while len(stack) >= 2:
		if stack[-2:] == "()":
			stack = stack[:-2]
		else:
			break

l = stack.count(")")
r = stack.count("(")
ans = "(" * l + s + ")" * r
print(ans)

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

add_l = 0
add_r = 0

for e in s:
	if e == "(":
		add_r += 1

	else: 
		if add_r == 0:
			add_l += 1
		else:
			add_r -= 1

ans = add_l * "(" + s + ")" * add_r
print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    

    


    N = int(input())
    S = input().rstrip()
    t = S
    while 1:
        a = len(t)
        s = t.split('()')
        s = ''.join(s)
        if len(s)==a:
            break
        t = s
    left = s.count(')')
    right = s.count('(')
    print('('*left + S + ')'*right)

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    




if __name__ == '__main__':
    main()

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

cnt = [0, 0]
for s in S:
    if s == "(":
        cnt[0] += 1
    else:
        if cnt[0]:
            cnt[0] -= 1
        else:
            cnt[1] += 1

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

Solution (Python):


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

def main():
    mod=10**9+7
    N=I()
    S=input()
    
    st=0
    a=""
    b=""
    for i in range(N):
        s=S[i]
        if st==0 and s==")":
            a+="("
        elif s=="(":
            st+=1
        else:
            st-=1
    b+=")"*st
    print(a+S+b)

main()

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

count = 0
flag = False

for index, s in enumerate(S):
  if s == '(':
    flag = True
    count += 1

  if flag and s == ')' and count != 0:
    count -= 1

  if not flag:
    continue

if count > 0:
  S += ')' * count

count = 0
flag = False

for index, s in enumerate(S[::-1]):
  if s == ')':
    flag = True
    count += 1

  if flag and s == '(' and count != 0:
    count -= 1

  if not flag:
    continue

if count > 0:
  S = '(' * count + S

print(S)

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

left_count = 0
right_count = 0
dif = 0

for i in range(len(s)):
    if s[i] == '(':
        left_count += 1
    elif s[i] == ')':
        if left_count > 0:
            left_count -= 1
        else:
            right_count += 1

ans = '(' * right_count  + s + ')' * left_count
print(ans)

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

Solution (Python):
import sys
input = sys.stdin.readline
from collections import Counter

N = int(input())
S = input().rstrip()
S_rev = S[::-1]

cnt = 0
left = 0
for i in S:
    if i == "(":
        cnt += 1
    elif cnt <= 0:
        left += 1
    else:
        cnt -= 1
S = "(" * left + S

cnt = 0
right = 0
for j in S_rev:
    if j == ")":
        cnt += 1
    elif cnt <= 0:
        right += 1
    else:
        cnt -= 1
S += ")" * right

print(S)

Solution (Python):

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

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

r_cnt, l_cnt = 0, 0

for s in S[::-1]:
    if s == ')':
        r_cnt += 1
    else:
        r_cnt = max(r_cnt-1, 0)

S = ['(']*r_cnt + S

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

S = S + [')']*l_cnt

print(*S, sep='')