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):
def main():
    N = int(input())
    S = input()
    pre = 0
    post = 0
    for i in range(N):
        if S[i] == '(':
            post += 1
        else:
            if post >= 1:
                post -= 1
            else:
                pre += 1
    print('(' * pre + S + ')' * post)


if __name__ == "__main__":
    main()

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

l, r = 0, 0
for s in S:
    if s == "(":
        l += 1
    elif l:
        l -= 1
    else:
        r += 1

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

Solution (Python):
N = input()
S = input()
st1 = []
st2 = []
tmp = ''
for x in S:
    if x == '(':
        st1.append(S)
    elif x == ')':
        if len(st1) > 0:
            st1.pop()
        else:
            tmp = '(' + tmp
    tmp += x
ans = tmp
for x in tmp[::-1]:
    if x == ')':
        st2.append(S)
    elif x == '(':
        if len(st2) > 0:
            st2.pop()
        else:
            ans += ')'
print(ans)

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

cnt = 0
res = ''
for i in range(n):
    if s[i] == '(':
        cnt += 1
    else:
        if cnt > 0:
            cnt -= 1
        else:
            res = '('+res
    res += s[i]

for j in range(cnt):
    res += ')'
print(res)

Solution (Python):
"""
"""

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


tmp, cnt = 0, 0

for i in s:
    if i == "(":
        tmp -= 1
    else:
        tmp += 1
    cnt = max(cnt, tmp)

ans = "(" * cnt + s


tmp, cnt = 0, 0
for i in s[::-1]:
    if i == "(":
        tmp += 1
    else:
        tmp -= 1
    cnt = max(cnt, tmp)

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

Solution (Python):

N=input()
S=raw_input()

st=[]
for s in S:
    if len(st) >= 1:
        a=st.pop()
        if a == '(' and s == ')':
            continue
        st.append(a)
    st.append(s)
migi=0
hidari=0
for s in st:
    if s == ")":migi+=1
    else: hidari+=1
print "("*migi + S + ")"*hidari

Solution (Python):

from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007






"""
f = [0]
for i in range(1,400):
    f.append(0)
for i in range(400,800):
    f.append(1)
for i in range(800,1200):
    f.append(2)
for i in range(1200,1600):
    f.append(3)
for i in range(1600,2000):
    f.append(4)
for i in range(2000,2400):
    f.append(5)
for i in range(2400,2800):
    f.append(6)
for i in range(2800,3200):
    f.append(7)
for i in range(3200,4801):
    f.append(-1)
n = I()
a = LI()
k = [1 for i in range(8)]
s = 0
t = 0
for i in a:
    if f[i] >= 0:
        if k[f[i]]:
            k[f[i]] = 0
            s += 1
    else:
        t += 1
print(max(s,1),min(s+t,n))
"""


n = I()
s = S()
ans = []
k = 0
for i in range(n):
    if s[i] == ")":
        k += 1
    else:
        if k > 0:
            ans += ["("]*k
            k = 0
        k -= 1
if k < 0:
    ans += [")"]*(-k)
else:
    ans = ["("]*k+ans
i = 0
if len(ans) == 0:
    for i in s:
        print(i,end = "")
else:
    while ans[i] == "(":
        i += 1
        if i == len(ans):break
    for j in range(n):
        ans.insert(i+j,s[j])
    for i in ans:
        print(i,end = "")
print()

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

d = [0]
for _s in s:
  if _s == '(':
    d.append(d[-1] + 1)
  else:
    d.append(d[-1] - 1)
x = min(d[1:])
ds = d[-1]

if x > 0:
  print('(' * (-x) + s + ')' * (ds))
else:
  print('(' * (-x) + s + ')' * (ds - x))

Solution (Python):
input()
s=input()
while 1:
  for i in range(len(s)):
    if s[i]=='('and s[i:].count(')')<(len(s)-i)/2:
      s+=')'
      break
  else:
    break
print('('*(s.count(')')-s.count('('))+s)

Solution (Python):
input()
s=input()
while 1:
  for i in range(len(s)):
    if s[i]=='('and s[i:].count(')')<(len(s)-i)/2:
      s+=')'
      break
  else:
    break
print('('*(s.count(')')-s.count('('))+s)

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

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

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

p = s.count('(')
q = n - p

if left + p < right + q:
    left += (right + q) - (left + p)
elif left + p > right + q:
    right += (left + p) - (right + q)

s = ['('] * left + s + [')'] * right

print(''.join(s))

Solution (Python):
def d_insertion(N, S):
    need_left, need_right = 0, 0  
    for c in S:
        if c == '(':
            
            
            need_right += 1
        else:
            if need_right == 0:
                need_left += 1  
            else:
                need_right -= 1
    return '(' * need_left + S + ')' * need_right

N = int(input())
S = input()
print(d_insertion(N, S))

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

flag = True
while flag is True:
    Snum = {"(": 0, ")": 0}
    flag = False
    for s in S:
        if s == ")":
            Snum["("] -= 1
        elif s == "(":
            Snum["("] += 1

        if Snum["("] < 0:
            S = "(" + S
            flag = True
            break
    else:
        S += ")" * (S.count("(") - S.count(")"))

print(S)

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

Solution (Python):
N = int(input())
L = input()
lst = [0]*(N)
n = 0
for i in range(N):
  if L[i] == "(":
    n += 1
  else:
    n -= 1
  lst[i] = n


if min(lst) < 0:
  ans = ""
  ans += "(" * ((-1)* min(lst))
  
  ans += L
  ans += ")" * (lst[-1]+ (-1)*min(lst))
else:
  ans = L
  ans += ")" * (lst[-1])
print(ans)

Solution (Python):
N = int(input())
S = input()
K = S
left = 0
right = 0
for i in range(N):
    if S[i] == "(":
        left += 1
    elif S[i] == ")":
        right = 1

    if right == 1 and left == 0:
        K = "(" + K
        right = 0
    elif right == 1 and left > 0:
        right = 0
        left -= 1

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

    if right == 0 and left == 1:
        K = K + ")"
        left = 0
    elif right > 0 and left == 1:
        right -= 1
        left = 0
print(K)

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

cnt = 0
o = 0
for s in S:
    if s == '(':
        cnt -= 1
    else:
        cnt += 1
        if cnt > o:
            o = cnt
c = o - cnt
o, c = max(o, 0), max(c, 0)

ans = '(' * o + S + ')' * c
print(ans)

Solution (Python):
a = int(input())
b = input()
s = b
c = 0
for i in range(a):
    if b[i] == "(":c+=1
    elif b[i] == ")" and c>0:c-=1
    else:
        s="("+s
s = s+")"*c
print(s)

Solution (Python):
N=int(input())
S=input()
l=[]

for s in S:
    if not l:
        l.append(s)
    else:
        t=l[-1]
        if t=="(" and s==")":
            l.pop()
        else:
            l.append(s)

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

Solution (Python):
N = int(input())
S = input()
cnt = 0
putLeft = 0
for si in S:
    if si=="(":
        cnt += 1
    else:
        cnt -= 1
    if cnt < 0:
        cnt = 0
        putLeft += 1
putRight = cnt
print("("*putLeft + S + ")"*putRight)

Solution (Python):
n = int(input())
s = input()
count_left = 0
count_right = 0
need_left = 0 
need_right = 0
for i in range(n):
  if s[i]==")":
    count_right += 1
  else:
    count_right -= 1
  need_left = max(need_left,count_right)

for i in range(n)[::-1]:
  if s[i]=="(":
    count_left += 1
  else:
    count_left -= 1
  need_right = max(need_right,count_left)
  
print("("*need_left+s+")"*need_right)

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


lList = []
rList = []
diffcount = 0
cacheS = ''
for x in S:
    cacheS = cacheS + x
for i, x in enumerate(cacheS):
    if x == '(':
        lList.append(i)
        diffcount += 1
    else:
        if diffcount > 0:
            rList.append(i)
            diffcount -= 1
        else:
            S = '(' + S

if 0 < diffcount:
    for i in range(diffcount):
        S = S + ')'
else:
    for i in range(diffcount):
        S = '(' + S

print(S)

Solution (Python):
N = input()

S = raw_input()
sample = [i for i in S]

i = 0
while i < len(sample)-1:
    if sample[i] == '(' and sample[i+1] == ')':
        del sample[i],sample[i]
        i = -1
    i += 1

S = '('*sample.count(')')+S+')'*sample.count('(')
print S

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

Solution (Python):
n = int(input())
s = input()
cnt = 0
dep = 10**10
for c in s:
    if c == '(':
        cnt += 1
    else:
        cnt -= 1
    dep = min(dep, cnt)
s = '(' * max(0, -dep) + s
cnt = 0
for c in s:
    if c == '(':
        cnt += 1
    else:
        cnt -= 1
s = s + ')' * cnt
print(s)

Solution (Python):
def splitter(s):
    cnt = 0
    prev = None
    ret = []
    for c in s:
        if prev is None:
            prev = c
            cnt = 1
            continue
        if c == prev:
            cnt += 1
        else:
            ret.append([cnt, prev])
            cnt = 1
            prev = c
    ret.append([cnt, prev])
    return ret

n = int(input())
s = input()
a = splitter(s)

left = 0
right = 0

if a[0][1] == ")":
    left += a[0][0]
    a.pop(0)

prev = 0
for i in a:
    if i[1] == ")":
        if prev > i[0]:
            prev -= i[0]
        else:
            left += i[0] - prev
            prev = 0
    else:
        prev += i[0]
right = prev

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

Solution (Python):
def solve(N, S):
    
    balance = 0
    start = 0
    for i in range(N):
        if S[i] == ")":
            if balance == 0:
                start += 1
            else:
                balance -= 1
        else:
            balance += 1
    return "(" * start + S + ")" * balance

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

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

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

left = 0
right = 0
out = ""
for i in range(len(s)):
    if s[i] == "(":
        left += 1
        out += "("
    else:
        right += 1
        out += ")"
        if right > left:
            out = "(" + out
            left += 1
while left != right:
    if right > left:
        left += 1
        out = "(" + out
    else:
        right += 1
        out += ")"
print(out)

Solution (Python):
n = (int)(input())
s = input()
l = len(s)
d_l = [0]*(l+1)
for i in range(1, l+1):
    d = s[:i]
    n_open = d.count('(')
    d_l[i] = 2*n_open - i

x = min(d_l)

print('('*(-x) + s + ')'*(d_l[-1]-x))

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

n=0
cnt=0	
prev=0

for x in S:
	if x=="(":
		n+=1
	else:			
		n=max(n-1,0)
	if n==0:
		if prev!=1:
			cnt+=1
	prev=n


print "("*cnt+S+")"*n

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

stack = 0
for i in range(n):
	c = str[i]
	if(c == '('):
		stack += 1
	elif(stack == 0):
		ans = '(' + ans
	else:
		stack -= 1

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

print(ans)

Solution (Python):


import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from collections import deque

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

ans = deque()
tmp = ''
l = r = 0
for c in S:
    if c == '(':
        l += 1
        tmp += '('
    else:
        if l == 0:
            ans.appendleft('(')
            ans.append(')')
        else:
            r += 1
            tmp += ')'
            if l == r:
                ans.append(tmp)
                tmp = ''
                l = r = 0
if l > r:
    tmp += ')' * (l-r)
    ans.append(tmp)
print(''.join(ans))

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


L,R = 0,0

rem = 0

for s in S:
    
    if s==")":
        if rem==0:
            L += 1
        else:
            R -= 1
            rem -= 1
    
    else:
        R += 1
        rem += 1

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

Solution (Python):
n = int(input())
s = input()
right = 0
left = 0
for i in s:
  if i == "(":
    right += 1
  else:
    if right > 0:
      right -= 1
    else:
      left += 1
print(left*'('+s+right*')')

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

X = 0
ans = ''

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

    if X < 0:
        ans += '('
        X = 0

ans += S + X * ')'
print(ans)

Solution (Python):

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


def func_cnt(str):
    cntlist = []
    tmp = 0
    for s in str:
        if s == "(":
            tmp += 1
        else:
            tmp -= 1
        cntlist.append(tmp)
    
    return cntlist


cntlist = func_cnt(S)

while min(cntlist) < 0:
    S = "(" * abs(min(cntlist)) + S
    cntlist = func_cnt(S)

S = S + ")" * cntlist[-1]

print(S)

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

s_list = [0 for _ in range(N)]
answer = S
stack = []
for i in range(N):
    if len(stack) == 0 and S[i] == ")":
        answer = "(" + answer
    elif len(stack) != 0 and S[i] == ")":
        stack.pop()
    else:
        stack.append(S[i])

print(answer + len(stack) * ")")

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

Solution (Python):
N = int(input())
S = input()
output = ''
lr = 0
for s in S[::-1]:
  lr += 1 if s == ')' else -1
  if lr < 0:
    output += ')'
    lr = 0
  output = s + output
print('(' * lr + output)

Solution (Python):

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

stack = []
for i in range(n):
    if s[i]=="(":
        stack.append("(")
    else:
        if len(stack)==0:
            stack.append(")")
        elif stack[-1]=="(":
            stack.pop()
        else:
            stack.append(")")

lcnt = 0
rcnt = 0
for c in stack:
    if c=="(":
        rcnt += 1
    else:
        lcnt += 1
print(("("*lcnt) + s + (")"*rcnt))

Solution (Python):
def bra(st):
    cc = 0
    res = st
    for le in st:
        if le == "(":
            cc += 1
        elif le == ")":
            cc -= 1
            if cc < 0:
                res = "(" + res
                cc = 0
    if cc == 0:
        return res
    else:
        res += ")" * cc
        return res

N = int(input())
S = input()
print(bra(S))

Solution (Python):
n = int(input())
s = input()
c = 0
sl = 0
lli =[]
rli =[]
k = 0
j = 0
for i in range(n):
    if i == 0:
        if s[i] == "(":
            lli.append(1)
            j = 1
        else:
            sl += 1
            k = 1
    elif s[i] == "(":
        k = 0
        if c == 1 or j == 1:
            lli[-1] += 1
            j = 0
        else:
            lli.append(1)
        c = 1
    else:
        if k == 1:
            sl += 1
        elif c == 2:
            if lli[-1] > 0:
                lli[-1] -= 1
            else:
                for v in range(len(lli)):
                    if lli[-1-v] > 0:
                        lli[-1-v] -= 1
                        break
                else:
                    rli[-1] += 1
        else:
            rli.append(0)
            lli[-1] -= 1
        c = 2

if sum(rli) + sl > 0 and sum(lli) > 0:
    print("(" * (sum(rli) + sl) + s + ")" * sum(lli))
elif sum(rli) + sl <= 0 and sum(lli) > 0:
    print(s + ")" * sum(lli))
elif sum(rli) + sl > 0 and sum(lli) <= 0:
    print("(" * (sum(rli) + sl) + s)
else:
    print(s)

Solution (Python):


N = input()
S = input()

cnt = 0
ans = S

for c in S:
    if c == '(':
         cnt += 1
    elif c == ')':
        cnt -= 1

    if cnt < 0:
        ans = '(' + ans
        cnt += 1

if cnt > 0:
    for i in range(cnt):
        ans = ans + ')'

print(ans)

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

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

cnt=0
L=0
for x in S:
    if x=='(':
        cnt+=1
    elif cnt>0:
        cnt-=1
    else:
        L+=1

print('('*L+S+')'*cnt)

Solution (Python):
n = input()
s = raw_input().strip()
c = 0
o = 0
for i in range(n):
    if s[i] == '(':
        c += 1
    else:
        if not c:
            o += 1
        else:
            c -= 1
ans = '('*(o)+s+')'*c
print ans

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

Solution (Python):
N=int(input().strip())
S=input().strip()
x=[0]
lc=0
rc=0
for i in range(len(S)):
    if S[i]=='(':
        lc+=1
    elif S[i]==')':
        rc+=1
    x.append(lc-rc)

xn=min(x)
d=lc-rc

ans='('*(-xn)+S+')'*(d-xn)

print(ans)

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

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

front = 0
for s in S:
    X += (s == "(")
    X -= (s == ")")

    if X < 0:
        X = 0
        front += 1
else:
    back = X

print("(" * front + S + ")" * back)

Solution (Python):
n = input()
s = input()
lcnt = 0
rcnt = 0
for i in s:
  if i == '(':
    rcnt+=1
  else :
    if rcnt == 0:
      lcnt += 1
    else:
      rcnt -= 1
for i in range(lcnt):
  s = '(' + s
for i in range(rcnt):
  s = s + ')'
print(s)

Solution (Python):
input()
S = input()
oc, cc = 0, 0
ans = ''
for s in S:
    if s == '(':
        oc += 1
        ans += s
    else:
        cc += 1
        if cc > oc:
            ans = '(' + ans
            oc += 1
        ans += ')'

print(ans + ')' * (oc - cc))

Solution (Python):

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

left, right = ([0] * 2)

for kakko in S:
    if kakko is "(":
        left += 1
    elif kakko is ")":
        if left is not 0:
            left -= 1
        else:
            right += 1

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

Solution (Python):
n = int(input())
s = input()
i = 0
k = 0
while i < len(s):
  if s[i] == "(":
    k += 1
  else:
    if k > 0:
      k -= 1
    else:
      s = "(" + s
      i += 1
  i += 1
print(s+")"*k)

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

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

n_left = 0
ans = s
for i in range(n):
  if s[i] == '(':
    n_left += 1
  elif s[i] == ')':
    if n_left == 0:
      ans = '(' + ans
    else:
      n_left -= 1
for i in range(n_left):
  ans += ')'
print(ans)

Solution (Python):


N = int(input())

S = input()

count = 0
count_list = []
for i in range(N):
    if S[i]=="(":
        count-=1
    if S[i]==")":
        count+=1
    count_list.append(count)

mr=max(count_list)

count = 0
count_list = []
for i in range(N):
    if S[N-i-1]=="(":
        count+=1
    if S[N-i-1]==")":
        count-=1
    count_list.append(count)


ml=max(count_list)

for _ in range(ml):
    S+=")"
for _ in range(mr):
    S="(" + S
    
print(S)

Solution (Python):
def insertion(S):
    Sc = S
    Scc = Sc.replace("()", "")
    while Scc != Sc:
        Sc = Scc
        Scc = Scc.replace("()", "")

    
    
    if len(Sc) == 0:
        Sl, Sr = "", ""
    elif Sc[0] != Sc[-1]:
        pos = Sc.find(")(")
        Sl = insertion(Sc[:pos+1])[0]
        Sr = insertion(Sc[pos+1:])[2]
    elif Sc[0] == '(':
        Sl = ""
        Sr = ')' * len(Sc)
    else:
        Sl = '(' * len(Sc)
        Sr = ""

    return Sl, S, Sr

N = int(input())
s = insertion(input())
print(s[0]+s[1]+s[2])

Solution (Python):

from collections import Counter

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

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

cnt = Counter(s)
print('(' * cnt[')'] + s_start + ')' * cnt['('])

Solution (Python):
N = input()
s = input()
s1 = s
s2 = ''
while s1 != s2: 
    s2 = s1
    s1 = s1.replace('()','')
s2 = s1.replace('(','')

print(len(s2)*'(' + s + (len(s1)-len(s2))*')')

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

count = 0
l = 0
for i in range(len(S)):
    if S[i] == '(':
        count += 1
    else:
        if count == 0:
            l += 1
        else:
            count -= 1
S = '('*l + S
S = S[::-1]

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

S = ')'*r + S
print(S[::-1])

Solution (Python):
n=int(input())
s=input()
x=[]
y=0
for i in range(n):
    if s[i]=="(":
        x.append("(")
        y+=1
    elif y>0:
        x.append(")")
        y-=1
    else:
        x.append(")")
        x=["("]+x
x=x+[")"]*y
print("".join(x))

Solution (Python):


N = int(input())
S = input()
open_cnt = 0
cnt = 0
open_flg = True
for i in range(N):
    if S[i] == '(':
        if not open_flg:
            if cnt < 0:
                cnt = 0
        cnt += 1
    else:
        open_flg = False
        cnt -= 1
        if cnt < 0:
            open_cnt += 1
cnt = 0
close_flg = True
close_cnt = 0
for i in range(N-1, -1, -1):
    if S[i] == ')':
        if not close_flg:
            if cnt < 0:
                cnt = 0
        cnt += 1
    else:
        close_flg = False
        cnt -= 1
        if cnt < 0:
            close_cnt += 1
print('(' * open_cnt + S + ')' * close_cnt)

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

def insertRecursively(string):
    for i in range(0, len(string)):
        part = string[0:i + 1]
        if 2 * part.count(')') > len(part):
            return insertRecursively('(' + string)
    if 2 * string.count('(') > len(string):
        return insertRecursively(string + ')')
    return string

print(insertRecursively(s))

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

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

Solution (Python):
def ABC064D():
    N = int(input())
    S = list(input())
    cnt = 0
    start = 0
    for i in S:
        if i == "(":
            cnt += 1
        elif i == ")":
            cnt -= 1
        if cnt < 0:
            start += 1
            cnt += 1
    tmp = []
    for i in range(start):
        tmp.append("(")
    S = tmp + S
    cnt_start = 0
    cnt_end = 0
    for i in S:
        if i == "(":
            cnt_start += 1
        elif i == ")":
            cnt_end += 1
    tmp = []
    for i in range(cnt_start - cnt_end):
        tmp.append(")")
    S = S + tmp

    for i in S:
        print(i, end = "")
    print()
ABC064D()