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=input()
mae=0
ushi=0
ans0=0
ans1=0
ans01=[]
flag=False
for i in range(n):
    ans01.append(s[i])
    if s[i]=='(':
        mae+=1
        flag=True
        ans1+=1
    else:
        ushi+=1
        if flag:
            ans1-=1
            if ans1<=0:
                flag=False
    ans0=max(ushi-mae,ans0)
ans00=[]
ans11=[]
for i in range(ans0):
    ans00.append('(')
for i in range(ans1):
    ans11.append(')')

print(''.join(ans00+ans01+ans11))

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

cnt = 0
for i,s in enumerate(S):
    if cnt < 0:
        ans = ['('] + ans
        cnt = 0
    if s == '(':
        cnt += 1
    else:
        cnt -= 1
if cnt> 0:
    ans = ans + [')'] * cnt
elif cnt < 0:
    ans = ['('] * (-cnt) + ans
print(''.join(ans))

Solution (Python):

def main():
    num = int(input())
    data = list(input())

    left, righ = 0, 0
    for i in range(num):
        ele = data[i]
        if ele == '(':
            righ += 1
        else:
            if righ > 0:
                righ -= 1
            else:
                left += 1

    ans = ['(' for i in range(left)] + data + [')' for i in range(righ)]
    print(''.join(ans))






if __name__ == '__main__':
    main()

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()

t = S

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

print("(" * t.count(")") + S + ")" * t.count("("))

Solution (Python):

import sys
sys.setrecursionlimit(300000)


def solve(N: int, S: str):
    pre = 0
    op = 0
    for c in S:
        if c == '(':
            op += 1
        elif c == ')':
            if op > 0:
                op -= 1
            else:
                pre += 1
    ret = (''.join(['(' for _ in range(pre)]) + S + 
           ''.join([')' for _ in range(op)]))
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    S = next(tokens)  
    solve(N, S)

if __name__ == '__main__':
    main()

Solution (Python):
from copy import deepcopy

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

i = 0
while 1:
    if i >= len(S):
        break
    if S[i] == "(":
        j = i
        while 1:
            if j >= len(S):
                break
            if S[j] == ")":
                S.pop(j)
                S.pop(i)
                i = -1
                break
            j += 1
    i += 1

y = S.count("(")
x = S.count(")")

print("(" * x + "".join(newS) + ")" * y)

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

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

if maxcount > 0:
    S = "(" * maxcount + S

count = 0
maxcount = 0

for i in range(len(S)):
    if S[i] == "(":
        count += 1
    else:
        count -= 1

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

print(S)

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

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

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

def main():
  n=I()
  s=S()

  c=0
  f=''
  e=''
  
  for x in s:
    if x=='(':
      c+=1
    else:
      c-=1

    if c<0:
      f+='('*abs(c)
      c=0

  if c<0:
    f+='('*abs(c)
  else:
    e+=')'*c

  return f+s+e

print(main())

Solution (Python):
n=int(input())
s=input()
s2=''
flag=0
cnt=0
for i in range(n):
  if flag==0:
    if s[i]=='(':
      flag=1
      cnt+=1
    elif s[i]==')':
      s2+=')'
  elif flag==1:
    if s[i]=='(':
      cnt+=1
    elif s[i]==')':
      cnt-=1
    if cnt==0:
      flag=0
if flag==1:
  s2+='('*cnt
cntl=0
cntr=0
for i in range(len(s2)):
  if s2[i]=='(':
    cntr+=1
  elif s2[i]==')':
    cntl+=1
ans='('*cntl+s+')'*cntr
print(ans)

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

leftStack = []
for i in range(len(S)):
    s = S[i]
    if s == "(":
        leftStack.append(s)
    elif s == ")":
        if len(leftStack) > 0:
            leftStack.pop()
        else:
            ans = "(" + ans

for i in range(len(leftStack)):
    ans = ans + ")"
print(ans)

Solution (Python):
from functools import reduce


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



a, b = reduce(
    lambda acc, s:
        (
            (
                acc[0] + 1 if s == '(' else
                max(0, acc[0] - 1)
            ),
            (
                acc[1] + 1 if s == ')' and acc[0] == 0 else
                acc[1]
            )
        ),
    S,
    (0, 0)
)
ans = b * '(' + S + a * ')'


print(ans)

Solution (Python):
from functools import reduce


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



a, b = reduce(
    lambda acc, s: (
        (
            acc[0] + 1 if s == '(' else
            max(0, acc[0] - 1)
        ),
        (
            acc[1] + 1 if s == ')' and acc[0] == 0
            else acc[1]
        )
    ),
    S,
    (0, 0)
)
ans = b * '(' + S + a * ')'


print(ans)

Solution (Python):
N = input()

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

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

tmp = s
for _ in range(50):
  tmp = tmp.replace("()", "")

l = tmp.count("(")
r = tmp.count(")")

for _ in range(l):
  s = s+")"
  
for _ in range(r):
  s = "(" + s
  
  
print(s)

Solution (Python):
kakko=[0]*(int(input())+1)
S=input()
kakkoSum=0
for n,s in enumerate(S):
    if s=="(":
        kakkoSum +=1
    else:
        kakkoSum -=1
    kakko[n+1] = kakkoSum
D=min(kakko)
if D<0:
    d=kakko[-1]
    kakkoleft=-D
    kakkoright=-D+d
    print("(" * kakkoleft + S + ")" * kakkoright)
elif kakko[-1] ==0:print(S)
else:
    d=kakko[-1]
    print(S + ")"* d)

Solution (Python):
n = int(input())
s = input()
open_ = 0
close_ = 0
for char in s:
    if char == "(":
        open_ += 1
    else:
        if open_ > 0:
            open_ -= 1
        else:
            close_ += 1
for i in range(open_):
    s += ")"
for i in range(close_):
    s = "(" + s
print(s)

Solution (Python):
import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip()

cnt = 0
ans = ''
for c in S:
    if c == '(':
        cnt += 1
    if c == ')':
        cnt -= 1
    if cnt < 0:
        cnt += 1
        ans += '('
ans += S + ')' * cnt
print(ans)

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

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

left = 0
max_left = 0

for i in S:
    if i == ')':
        left += 1
        max_left = max(max_left, left)
    else:
        left -= 1

right = 0
max_right = 0

for i in S[::-1]:
    if i == '(':
        right += 1
        max_right = max(max_right, right)
    else:
        right -= 1

ans = '(' * max_left  + S +  ')' * max_right

print(ans)

Solution (Python):
N = int(input())
S = input()
addleft = 0
countleft = 0
for i in range(0, N):
	if S[i] == '(':
		countleft += 1
	if S[i] == ')':
		if countleft == 0:
			addleft += 1
		else:
			countleft -= 1
for i in range(0, addleft):
	S = '(' + S
for i in range(0, countleft):
	S = S + ')'
print(S)

Solution (Python):
n = int(input())
s = input()
cnt = 0
cnt_start = 0
for i in range(n):
    if '(' in s[n-i-1]:
        if cnt > 0:
            cnt -= 1
        else:
            cnt_start += 1
    else:
        cnt += 1
for i in range(cnt_start):
    s = s+')'
for j in range(cnt):
    s = '('+s
print(s)

Solution (Python):











import sys
input=sys.stdin.readline
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [input() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    S = ST()
    imos = []
    for s in S:
        if s == "(":
            imos.append(1)
        else:
            imos.append(-1)
    status = [0]
    head = ""
    tail = ""
    for imo in imos:
        appp = status[-1] + imo
        if appp < 0:
            head += "("
            appp = 0
        status.append(appp)
    if status[-1] > 0:
        tail = ")" * status[-1]
    print(head+S+tail)
if __name__ == '__main__':
    main()

Solution (Python):







from collections import* 
from fractions import gcd
from functools import* 
from itertools import* 
from operator import mul,itemgetter
from bisect import* 
from heapq import* 
from math import factorial,pi
from copy import deepcopy
import sys

sys.setrecursionlimit(10**8)

def main():
    input()
    s=input()
    t=s
    while "()"in s:
        s=s.replace("()","")
    n,m=s.count(")"),s.count("(")
    s=n*"("+t+m*")"
    print(s)
if __name__ == '__main__':
    main()

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

li_start = []
li_end = []
for ind,i in enumerate(S):
    if(i=='('):
        li_start.append(ind)
    else:
        if(len(li_start)>0):
            li_start.pop(-1)
        else:
            li_end.append(ind)
print('('*len(li_end)+S+')'*len(li_start))

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

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

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

print("("*lmax + s + ")"*rmax)

Solution (Python):
import collections

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

num_open = 0
num_close = 0

q = collections.deque([])

for i in range(N):
  if S[i] == "(":
    q.append("(")
  if S[i] == ")":
    if len(q) == 0:
      num_close += 1
    else:
      q.pop()

num_open = len(q)
str_close = "(" * num_close
str_open =  ")" * num_open


ans = str_close + S + str_open

print(ans)

Solution (Python):
n = int(input())
s = input()
num_overopen = 0
num_overclose = 0
import collections
q = collections.deque([])
for i in range(n):
    if s[i] == "(":
        q.append("(")
    if s[i] == ")":
        if len(q) == 0:
            num_overclose += 1
        else:
            q.pop()
print( ("(" * num_overclose) + s + (")" * len(q)))

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

Solution (Python):
n = int(input())
s = list(input())
s1 = [1 if si=='(' else -1 for si in s]
cnt1=0
cnt2=0
ans1=0
ans2=0
for i in range(n):
    if s1[i]==1and cnt2>0:
        ans2+=cnt2
        cnt2 = 0
    cnt2+=-s1[i]
if cnt2>0:
    ans2+=cnt2
for i in range(n)[::-1]:
    if s1[i]==-1and cnt1>0:
        ans1+=cnt1
        cnt1 = 0
    cnt1+=s1[i]
if cnt1>0:
    ans1+=cnt1
s=['(']*ans2+s+[')']*ans1
print(''.join(s))

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

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

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

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

Solution (Python):
N=int(input())
S=input()
a=0
b=0
for i in S:
    if i=="(":
        if b>0:
            a+=b
            b=0
        b-=1
    if i==")":
        b+=1
a+=max(b,0)
S="("*a+S
a=0
b=0
for i in S[::-1]:
    if i==")":
        if b>0:
            a+=b
            b=0
        b-=1
    if i=="(":
        b+=1
a+=max(b,0)
S+=")"*a
print(S)

Solution (Python):
n=int(input())
s=list(input())
l=0
r=0
al=0
ar=0
for i in range(n):
    if s[i]=='(':
        l+=1
    else:
        if l>0:
            l-=1
        else:
            al+=1
for i in range(n-1,-1,-1):
    if s[i]==')':
        r+=1
    else:
        if r>0:
            r-=1
        else:
            ar+=1
            
ans=''
for i in range(al):
    ans+='('
for i in range(n):
    ans+=s[i]
for i in range(ar):
    ans+=')'
print(ans)

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

Solution (Python):
n = int(input())
S = list(input())
ANS = []
a = 0
b = 0
for s in S:
    ANS.append(s)
    if s == '(':
        a += 1
        
    else:
        b += 1
        if a<b:
            a += 1
            ANS.insert(0,'(')
        
for i in range(a-b):
    ANS.append(')')
print("".join(ANS))

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

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

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

Solution (Python):
n = int(input())
s = input()
x, y, a = 0, 0, 0

for char in s:
    if char == '(': x += 1
    else: y += 1
    a = min(a, x-y)
    b = x-y

ans = '('*(-a) + s + ')'*(b-a)
print(ans)

Solution (Python):


import itertools
from collections import Counter
from collections import defaultdict
import bisect
import math
import heapq

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

    need_left = 0
    need_right = 0
    for s in S:
        if s == '(':
            need_right += 1
        else:
            if need_right == 0:
                need_left += 1
            else:
                need_right -= 1

    ans = '(' * need_left + S + ')' * need_right
    print(ans)


if __name__ == '__main__':
    main()

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

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

print ( "("*( max(-mi,0) ) + S + ")"*( max(c-mi,0)  ) )

Solution (Python):
n = int(input())
s = input()
ans = s
stack = []
for i in range(n):
    if s[i] == '(':
        stack.append(i)
    else:
        if stack == []:
            ans = '(' + ans
        else:
            stack.pop()
ans += ')' * len(stack)
print(ans)

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

left = 0
stack = []
for i in range(n):
    if s[i] == '(':
        stack.append('(')
    else:
        if len(stack) == 0:
            left += 1
        else:
            stack.pop()
right = len(stack)

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

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

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

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

pares = S[:]

counter = 0
pares_num = []
for s in pares:
    if s == '(':
        counter += 1
        pares_num.append(counter)
    else:
        counter -= 1
        pares_num.append(counter)
        
min_num = min(pares_num)
if min_num < 0:
    pares = '(' * (-1*min_num) + pares
    

counter = 0
pares_num = []
for s in pares:
    if s == '(':
        counter += 1
        pares_num.append(counter)
    else:
        counter -= 1
        pares_num.append(counter)



pares += ')' * pares_num[-1]


print(pares)

Solution (Python):
from functools import reduce


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



a, b = reduce(
    lambda acc, s: (
        (
            acc[0] + 1 if s == '(' else max(0, acc[0] - 1),
            acc[1] + 1 if s == ')' and acc[0] == 0 else acc[1]
        )
    ),
    S,
    (0, 0)
)
ans = b * '(' + S + a * ')'


print(ans)

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

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

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

l = 0
r = 0

i = 0
for s in S:
    if s =='(':
        i += 1
    else:
        i -= 1
        if i < 0:
            i += 1
            l += 1

print('('*l+''.join(S)+')'*i)

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

T = [+1 if s=='(' else -1 for s in S]

from itertools import accumulate
Tcumsum = list(accumulate(T))

i = max(0, - min(Tcumsum))

print('(' * i + S + ')' * (Tcumsum[-1]+i))

Solution (Python):
N = int(input())
S = input()
left = 0
right = 0
k = 0
for c in S:
    if c == "(":
        left += 1
    else:
        right += 1
        if left < right:
            left = right
            k += 1
ans = ""
for i in range(k):
    ans += "("
ans += S
for i in range(left-right):
    ans+=")"
print(ans)

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

before = 0
after = 0
for i in s:
    if i == '(':
        after += 1
    elif i == ')':
        if after > 0:
            after -= 1
        else:
            before += 1

print('('*before + s + ')'*after)

Solution (Python):
N = int(input())
S = input()
m = [0,0]

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

for i in range(m[0]):
    S += ')'
for i in range(m[1]):
    S = '(' + S

print(S)

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math

mod = 10**9+7


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


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

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

Solution (Python):
N = int(input())
S = input()
cnt = 0
cnt1 = 0
for s in S:
    if s == "(":
        cnt += 1
    else:
        cnt -= 1
    if cnt < 0:
        cnt1 += 1
        cnt = 0
ans = ("("*cnt1) + S + (")"*cnt)
print(ans)

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

l = 0
p = 0
for i in range(n):
    if s[i]=='(':
        l+=1
    elif l>0:
        p+=1
        l-=1

a = s.count('(')
b = s.count(')')

print('('*(b-p)+s+')'*(a-p))

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

def solve(s):
  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
  return '(' * add_left + s + ')' * add_right

ans = solve(S)
print(ans)

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

Solution (Python):

import sys


def solve(N: int, S: str):
    left = 0
    left_max = 0
    for i in range(N):
        if S[i] == ')':
            left += 1
        elif S[i] == '(':
            left -= 1
        if left > left_max:
            left_max = left
    
    right = 0
    right_max = 0
    for i in range(N-1, -1, -1):
        if S[i] == '(':
            right += 1
        elif S[i] == ')':
            right -= 1
        if right > right_max:
            right_max = right
    print('(' * left_max + S + ')' * right_max)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    S = next(tokens)  
    solve(N, S)

if __name__ == '__main__':
    main()

Solution (Python):
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n = f()[0]
    s= input().strip()


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

    for i in range(cnt_inbal):
        s = '(' + s


    for i in range(cnt_l + cnt_inbal - (n - cnt_l)):
        s += ')'

    print(s)
        
        


solve()

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

right = 0
left = 0
for i in S:
    if i == '(':
        left += 1
    else:
        if left > 0:
            left -= 1
        else:
            right += 1

ans = ''
for i in range(right):
    ans += '('
ans += S
for i in range(left):
    ans += ')'

print(ans)

Solution (Python):
n = int(input())
s = input()
r = 0
lr = 0
li = 0
for i in range(n):
    if s[i] == '(':
        li = i
        break
    if i==n-1:
        li = i
for i in range(li, n):
    if s[i] == '(':
        lr += 1
    else:
        if lr > 0:
            lr -= 1
        else:
            r += 1

res = '('*r
res += '('*li
res = res + s + ')' * max(0, lr)
print(res)

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

def solve(n,s):
    cnt0 = [0]*n
    cnt1 = [0]*n
    cnt0[0] = 1 if s[0] == '(' else 0
    cnt1[-1] = 1 if cnt1[-1] == ')' else 0
    for i in range(1,n):
        cnt0[i] = cnt0[i - 1]
        if s[i] == '(' :
            cnt0[i] += 1
        elif cnt0[i] > 0:
            cnt0[i] -= 1
    return cnt0[-1]
        

right = solve(N,s)
r_s =''
for i in s:
    if i =='(':
        r_s = ')' + r_s
    else:
        r_s = '(' + r_s
left = solve(N,r_s)
print('('*left + ans + ')'*right)

Solution (Python):

N=int(input())
S=str(input())
Slist=list(S)
Left=[] 
Right=[] 
for i in range(N):
    if Slist[i] == "(":
        Left.append(i)
    else:
        if len(Left) == 0:
            Right.append(i)
        else:
            del Left[0]
Llen=len(Left)
Rlen=len(Right)
for i in range(Llen):
    Slist.insert(2*N,")")    
for i in range(Rlen):
    Slist.insert(0,"(")
ans="".join(Slist)
print(ans)

Solution (Python):
n = int(input())
s = input()
res = ""
stack = []
for c in s:
    if c=='(':
        res+=c
        stack.append(c)
    else:
        if stack==[]:
            res = '('+res+c
        else:
            stack.pop()
            res+=c
for c in stack:
    res+=')'
print(res)

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()

l = list(s)

value = 0
app_s = 0

for j in range(0,n):
    i = l[j]
    if i == "(":
        value = value + 1
    else:
        value = value - 1
        if -app_s > value:
            app_s = -value

if app_s > 0:
    for j in range(0,app_s):
        s = "(" + s

value = value + app_s

if value > 0:
    for j in range(0,value):
        s = s + ")"

print(s)

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

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

def check_rank(s):
    count = 0
    rank = [0] * len(s)
    for i, c in enumerate(s):
        if c == ")":
            count -= 1
        if c == "(":
            count += 1
        rank[i] = count
    return rank

r = check_rank(s)

if min(r) < 0:
    s = abs(min(r)) * "(" + s
    r = check_rank(s)

if r[-1] > 0:
    s = s + ")" * r[-1]
    r = check_rank(s)

print(s)

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

l_cnt = 0
for s in S[::-1]:
    if s == ')':
        l_cnt += 1
    elif s == '(':
        if l_cnt != 0:
            l_cnt -= 1

r_cnt = 0
for s in S:
    if s == '(':
        r_cnt += 1
    elif s == ')':
        if r_cnt != 0:
            r_cnt -= 1
            
print('(' * l_cnt + S + ')' * r_cnt)

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

need_left = 0
cnt = 0
for i in range(N):
    if s[i] == "(":
        cnt += 1
    else:
        if cnt == 0:
            need_left += 1
        else:
            cnt -=1
need_right = cnt
ans =""
for i in range(need_left):
    ans +="("
ans += s
for i in range(need_right):
    ans += ")"
print(ans)

Solution (Python):
n = input()
s = input()
ltmp = 0
ladd = 0
for c in s:
    if c == ")":
        if ltmp == 0:
            ladd += 1
        else:
            ltmp -= 1
    else:
        ltmp += 1
        
print("(" * ladd + s + ")" * ltmp)

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
s = ns()

stack = []

left = 0
right = 0

for si in s:
    if si == '(':
        stack.append('(')
        
    elif si == ')':
        if stack:
            stack.pop()
        else:
            left += 1
            
right = len(stack)

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

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

S = input()
while True:
	nl = 0
	nr = 0
	j = "O"
	for i in S:
		if i == "(":
			nl += 1
		else:
			nr += 1
		if nr > nl:
			S = "(" + S
			j = "N"
			break
	if j == "O":
		break

n = S.count("(") - S.count(")")
print(S + n * ")")

Solution (Python):
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    S = input().strip()
    
    L = ''
    R = ''
    c = 0
    for s in S:
        if s == '(':
            c += 1
        else:
            c -= 1

        if c < 0:
            L += '('
            c += 1

    R += ')' * c

    return L + S + R


if __name__ == '__main__':
    print(main())

Solution (Python):
n=int(input())
s=input()
t=s
while "()" in s:
    s=s.replace("()","")

print(s.count(")")*"("+t+")"*s.count("("))

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

Solution (Python):
n = int(input())
s = input()
lv = [0] * n

lvi = 0
for i,v in enumerate(s):
    if v == '(' :
        lvi += 1
    else:
        lvi -= 1
    lv[i] = lvi
l = min(0,min(lv))
r = -lv[-1] + l

print('('*(-l) + s + ')'*(-r))

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

Solution (Python):
def insertion(N: int, S: str)->str:
    bra, ket = 0, 0
    for c in S:
        if c == '(':
            bra += 1
        else:  
            if bra > 0:  
                bra -= 1
            else:  
                ket += 1

    ret = ('(' * ket) + S

    bra, ket = 0, 0
    for c in reversed(S):
        if c == ')':
            ket += 1
        else:  
            if ket > 0:  
                ket -= 1
            else:  
                bra += 1

    ret = ret + (')' * bra)

    return ret


if __name__ == "__main__":
    N = int(input())
    S = input()
    ans = insertion(N, S)
    print(ans)

Solution (Python):
n=int(input())
s=input()
d=[0,0]
for i in s:
    if i=="(": d[0]+=1
    if i==")" and d[0]>0: d[0]-=1
for i in s[::-1]:
    if i==")": d[1]+=1
    if i=="(" and d[1]>0: d[1]-=1
s="("*d[1]+s+")"*d[0]
print(s)

Solution (Python):
from collections import deque
N = int(input())
S = input()
dq = deque()
ans = deque(list(S))
for s in S:
    if not dq:
        dq.append(s)
    else:
        if dq[-1] == "(" and s == ")":
            dq.pop()
        else:
            dq.append(s)
while dq:
    value = dq.popleft()
    if value == ")":
        ans.appendleft("(")
    elif value == "(":
        ans.append(")")
ans = "".join(ans)
print(ans)

Solution (Python):
n = int(input())
s = list(input())
left = 0
right = 0
i = 0
while i < len(s):
    if s[i] == "(":
        left += 1
    else:
        right += 1
    if left < right:
        s.insert(0,"(")
        left += 1
        i += 1
    i += 1
for i in range(left-right):
    s.append(")")
for i in range(len(s)):
    if i != len(s)-1:
        print(s[i],end="")
    else:
        print(s[i])

Solution (Python):
N = int(input())
S = input()
r = []
for c in S:
  if c == "(":
    r.append(1)
  else:
    r.append(-1)
ruiseki = [0]
for er in r:
  ruiseki.append( ruiseki[-1] + er )

age = 0
if min(ruiseki) < 0:
  age = abs(min(ruiseki))
  S = "("*abs(min(ruiseki)) + S
if ruiseki[-1] + age > 0:
  S = S + ")"*(ruiseki[-1] + age)
print(S)

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

i = 0
c = 0
min_c = 0
while i < N:
    if S[i] == "(":
        c += 1
    else:
        c -= 1
    min_c = min(c, min_c)
    i += 1

print("(" * (-min_c) + S + ")" * (c-min_c))

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

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

Solution (Python):
n = int(input())
s = input()
que = []
for i in range(n):
  if s[i] == ")" and que and que[-1] == "(":
    que.pop()
  else:
    que.append(s[i])
ket = que.count(")")
bra = len(que) - ket
print("("*ket + s + ")"*bra)

Solution (Python):
n = int(input())
s = input()
count1 = 0  
count2 = 0  
ans = s
for i in range(n):
    if s[i] == "(":
        count1 += 1
    else:
        if count1 > 0:
            count1 -= 1
        else:
            count2 += 1

print("("*count2 + s + ")"*count1)