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():
    length = int(input())
    string = input()
    count = [0] * length
    min_value = 0
    for i in range(length):
        if i == 0:
            if string[i] == "(":
                count[i] = 1
            else:
                count[i] = -1
        elif string[i] == "(":
            count[i] = count[i - 1] + 1
        else:
            count[i] = count[i - 1] - 1
        min_value = min(min_value, count[i])
    print("(" * (-min_value) + string + ")" * (count[-1] - min_value))


if __name__ == '__main__':
    main()

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

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

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

l = 0
r = 0
for si in s:
    if si == "(":
        l  += 1
    else:
        if l == 0:
            r += 1
        else:
            l -= 1

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

Solution (Python):
N = int(input())
S = list(input())
stack = []
ans = S[::1]
r = 0
for c in S:
    if c == "(":
        r += 1
    if c == ")":
        if r > 0:
            r -= 1
        else:
            ans.insert(0, "(")
for _ in range(r):
    ans.append(")")
print("".join(ans))

Solution (Python):
N = int(input())
S = list(input())
stack = []
ans = S[::1]
add = 0
r, l = 0, 0
for i in range(N):
    c = S[i+add]
    if c == "(":
        r += 1
    if c == ")":
        if r > 0:
            r -= 1
        else:
            ans.insert(0, "(")
for _ in range(r):
    ans.append(")")
print("".join(ans))

Solution (Python):
N = int(input())
S = list(input())[::-1]
stack = []
ans = S[::1]
add = 0
r, l = 0, 0
for c in S:
    if c == ")":
        l += 1
    if c == "(":
        if l > 0:
            l -= 1
        else:
            ans.insert(0, ")")
for i in range(l):
    ans.append("(")
print("".join(ans[::-1]))

Solution (Python):
n = int(input())
s = input()
begin = 0
end = 0
for i in range(n):
    if s[i] == "(":
        begin += 1
    if s[i] == ")":
        if begin > 0:
            begin -= 1
            continue
        end += 1
print("("*end + s + ")"*begin)

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

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

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

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

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

c=s.count('()')
while c!=0:
  s=list(s)

  i=0
  n_s=''
  while i<=len(s)-1:
    if s[i]=='(' and s[i+1]==')':
      i+=2
    else:
      n_s+=s[i]
      i+=1

  s=''.join(n_s)
  c=s.count('()')

c_a=s.count('(')
c_b=s.count(')')

ans='('*c_b+ans+')'*c_a
print(ans)

Solution (Python):
N, S = open(0).read().split()
N = int(N)
cnt = 0
l = 0
for i in range(N):
  if S[i]=='(':
    cnt += 1
  else:
    if cnt==0:
      l += 1
    else:
      cnt -= 1
cnt = 0
r = 0
for i in range(N-1,-1,-1):
  if S[i]==')':
    cnt += 1
  else:
    if cnt==0:
      r += 1
    else:
      cnt -= 1
print('('*l+S+')'*r)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = onem()

s = input().split()[0]

ss = ""
co = 0
for i in range(n):
    if s[i] == ")" and co <= 0:
        ss = "(" + ss + ")"
    elif s[i] == ")":
        ss = ss + ")"
        co -= 1
    if s[i] == "(":
        co += 1
        ss = ss + "("
print(ss + ")" * co)

Solution (Python):
n=int(input())
s=input()
li=list(s)
leftWhichNeedsRight = [] 
RightWhichNeedsLeft = [] 
if li[0] == "(":
    leftWhichNeedsRight.append(1)
    RightWhichNeedsLeft.append(0)
if li[0] == ")":
    leftWhichNeedsRight.append(0)
    RightWhichNeedsLeft.append(1)
for i in range(1,n):
    c = li[i]
    l = leftWhichNeedsRight[i-1]
    r = RightWhichNeedsLeft[i-1]
    if c == "(":
        RightWhichNeedsLeft.append(r)
        leftWhichNeedsRight.append(l+1)
    elif c == ")":
        if l > 0:
            RightWhichNeedsLeft.append(r)
            leftWhichNeedsRight.append(l-1)
        else:
            RightWhichNeedsLeft.append(r+1)
            leftWhichNeedsRight.append(l)


print("("*RightWhichNeedsLeft[n-1]+s+")"*leftWhichNeedsRight[n-1])

Solution (Python):
input()
S = input()
left = right = 0
for c in S:
    if c == "(":
        left += 1
    else:
        if left:
            left -= 1
        else:
            right += 1
print("(" * right + S + ")" * left)

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

count = 0
left_num = 0

for p in parentheses:
    if p == '(':
        count += 1
    else:
        count -= 1

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

print('(' * left_num + parentheses + ')' * count)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n = int(readline())
s = readline().rstrip().decode('utf-8')

"""
左端に(を、右端に)を必要なだけ与えることで辞書順最小になる
"""

eight = 0
nine = 0
flag = 0
th = 0
res = 0
for i in s:
    if i == ")":
        if th:
            th -= 1
        else:
            res += 1
    elif i == "(":
        th += 1
res2 = 0
th = 0
for i in s[::-1]:
    if i == "(":
        if th:
            th -= 1
        else:
            res2 += 1
    elif i == ")":
        th += 1

s = "("*res + s + ")"*res2
print(s)

Solution (Python):
import sys


def main():
    N = int(input())
    S = input()
    lc,rc = 0,0
    for s in S:
        if s == "(":
            rc += 1
        else:
            if rc <= 0:
                lc += 1
            else:
                rc -= 1
    
    print("("*lc+S+")"*rc)            
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys


def main():
    N = int(input())
    S = str(input())
    left,right = 0,0
    for s in S:
        if s == "(":
            right += 1
        elif right <= 0:
            left += 1
        else:
            right -= 1
        
    print("("*left+S+")"*right)
  
if __name__ == "__main__":
    main()

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

l_num, r_num = 0, 0
for i in s:
    if i == '(':
        l_num += 1
    elif l_num <= 0:
        r_num += 1
    else:
        l_num -= 1
print('(' * r_num + s + ')' * l_num)

Solution (Python):
import copy
N = int(input())
S = input()
stack = []
ans = copy.deepcopy(S)
for s in S:
    if s == ")":
        if len(stack) > 0 and stack[-1] == "(":
            stack.pop()
        else:
            ans = "(" + ans
    elif s == "(":
        stack.append(s)
for _ in range(len(stack)):
    ans = ans + ")"
print(ans)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
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 [I() 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()
    head = 0
    tail = 0
    c,e = 0,0
    for s in S:
        if s=="(":
            c += 1
        else:
            e += 1
        if c<e:
            head += e-c
            e=c
    if c>e:
        tail = c-e
    print(head * "(" + S + tail * ")")
        
if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
S = list(map(str, input()))


left_stock = 0
left_short = 0

for s in S:
	if s == "(":
		left_stock += 1
	else:
		if left_stock > 0:
			left_stock -= 1
		else:
			left_short += 1
			
for _ in range(left_short):
	print("(", end = "")
for s in S:
	print(s, end = "")
for _ in range(left_stock):
	print(")", end = "")

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

RLE = []
now_char = S[0]
now_cnt = 1
for i in range(1, N):
    if now_char == S[i]:
        now_cnt += 1
    else:
        RLE.append([now_char, now_cnt])
        now_char = S[i]
        now_cnt = 1
RLE.append([now_char, now_cnt])


n = len(RLE)
ans = ""
left_cnt = 0
right_cnt = 0

for i in range(n):
    now_char = RLE[i][0]
    now_cnt = RLE[i][1]
    if now_char == "(":
        left_cnt += now_cnt
    else:
        right_cnt += now_cnt
        if right_cnt > left_cnt:
            ans += "(" * (right_cnt - left_cnt)
            right_cnt = 0
            left_cnt = 0
        else:
            left_cnt -= right_cnt
            right_cnt = 0

ans += S
if left_cnt > 0:
    ans += ")" * left_cnt

print(ans)

Solution (Python):
import copy

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

ans = copy.copy(s)

lens = 0
while lens != len(s):
    lens = len(s)
    for i in range(len(s)):
        if s[i:i+2] == '()':
            s = s[:i] + s[i+2:]

ans = '(' * s.count(')') + ans + ')' * s.count('(')

print(ans)

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n=int(input())
s=input()
i=0
leftcnt=0
rightcnt=0
for i in range(len(s)):
    if s[i]==")":
        if leftcnt==0:
            rightcnt+=1
        else:
            leftcnt-=1
    else:
        leftcnt+=1
print("("*rightcnt+s+")"*leftcnt)

Solution (Python):
import sys

input = sys.stdin.readline


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

    S2 = S

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

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

    print(y * "(" + S + x * ")")




if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
S = input()
s = S
l=0
r=0
tmp=0
flag = True
for i in range(N):
    
    if S[i]=="(":
        tmp=i
        r=1
        flag = False
        break
    else:
        l += 1

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

if r>0:
    for _ in range(r):
        s = s + ")"

if l>0:
    for _ in range(l):
        s = "(" + s

print(s)

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

l_lack=0
l_cnt=0

for tmp in s:
    if tmp==")":
        if l_cnt==0:
            l_lack+=1
        else:
            l_cnt-=1
    if tmp=="(":
        l_cnt+=1

left="("*l_lack
right=")"*l_cnt
print(left+s+right)

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

l_num, r_num = 0, 0
for i in s:
    if i == '(':
        l_num += 1
    elif l_num <= 0:
        r_num += 1
    else:
        l_num -= 1
print('(' * r_num + s + ')' * l_num)

Solution (Python):
N=int(input())
S=input()
a=0
b=0
cnt=0
for i in range(N):
  if S[i]==')':
    b+=1
  else:
    a+=1
  cnt=max(cnt,b-a)
A='('*cnt+S
d=A.count(')')
e=A.count('(')
f=e-d
print(A+')'*f)

Solution (Python):

_N = int(input())
S = input()

open_parenthesis = 0
left = 0
right = 0

for s in S:
    if s == '(':
        open_parenthesis += 1
    elif s == ')':
        if open_parenthesis != 0:
            open_parenthesis -= 1
        else:
            left += 1

right = open_parenthesis

ans = '(' * left + S + ')' * right

print(ans)

Solution (Python):
def test(length, cost):
    tmp = length.replace('()', '')
    if len(length) < 2 or len(tmp) == len(length):
        return length
    return test(tmp, len(length))

n = int(input())
s = input()
last = test(s, len(s))
print(last.count(')') * '(' + s + last.count('(') * ')')

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

tmp1, tmp2 = s, s
tmp1 = tmp2.replace('()', '')

while not (tmp1 == tmp2):
	tmp2 = tmp1
	tmp1 = tmp2.replace('()', '')


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

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

Solution (Python):

N=int(input())
S=list(input())
s1=[0]*N
s2=[0]*N
p=[0]*N
if S[0]=='(':
    s1[0]=1
else:
    s2[0]=1
for i in range(1,N):
    if S[i]=='(':
        s1[i]=s1[i-1]+1
        s2[i]=s2[i-1]
        p[i]=p[i-1]
    else:
        s1[i]=s1[i-1]
        s2[i]=s2[i-1]+1
        if s1[i]-p[i-1]>0:
            p[i]=p[i-1]+1
        else:
            p[i]=p[i-1]
if s1[N-1]-p[N-1]>0:
    S.append(')'*(s1[N-1]-p[N-1]))
if s2[N-1]-p[N-1]>0:
    l2='('*(s2[N-1]-p[N-1])
    S.insert(0,l2)
print(''.join(S))

Solution (Python):

N = int(input())
S = input()
op, cl, pair = [0], [0], [0]
for i in range(N):
    if S[i] == "(":
        op.append(op[-1]+1)
        cl.append(cl[-1])
    else:
        op.append(op[-1])
        cl.append(cl[-1]+1)
for i in range(1, N+1):
    if cl[i-1] < cl[i] and op[i] - pair[-1] > 0:
        pair.append(pair[-1] + 1)
    else:
        pair.append(pair[-1])
o, c, p = op[-1], cl[-1], pair[-1]
if o - p > 0:
    S = S + ")" * (o - p)
    if c - p > 0:
        S = "(" * (c - p) + S
    print(S)
elif c - p > 0:
    S = "(" * (c - p) + S
    print(S)
else:
    print(S)

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

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

ans = ''
ans += '(' * list(replaced).count(')')
ans += S
ans += ')' * list(replaced).count('(')

print(ans)

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

rb = s.count(')')
lb = s.count('(')

r=0
l=0
ll = 0
rr = 0
for c in s:
  if c =='(' :
    l += 1
  else:
    if l > 0:
      ll += 1
    l -= 1
    if l < 0:
      l = 0          
      
for c in s[::-1]:
  if c ==')' :
    r += 1
  else:
    if r > 0:
      rr += 1
    r -= 1
    if r < 0:
      r = 0
      
print('('*(rb - rr) + s + ')'*(lb - ll))

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

l = 0
r = 0

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

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

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

l = 0
r = 0

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


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

Solution (Python):
from sys import stdin
n = int(stdin.readline().rstrip())
s = stdin.readline().rstrip()
point = 0
point2 = 0
for i in s:
    if i == "(":
        point += 1
    else:
        if point:
            point -= 1
        else:
            point2 += 1
print("("*point2+s+")"*point)

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

c = 0
scount = 0
for i, si in enumerate(list(s)):
  if si == '(':
    c += 1
  else:
    c -= 1
  if c < 0:
    scount += 1
    c = 0

s = '('*scount + s
s = s + ')'*c
print(s)

Solution (Python):
n=int(input())
S=input()
A=[0]*n
for i in range(n):
  if S[i]=='(':
    A[i]=1
  else:
    A[i]=-1
A=[0]+A
for i in range(1,n+1):
  A[i]=A[i]+A[i-1]

m=min(A)
T='('*(A[0]-m)+S+')'*(A[-1]-m)
print(T)

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


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

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

left = "".join(["(" for _ in range(l_count)])
right = "".join([")" for _ in range(r_count)])

print(left+S+right)

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

from collections import defaultdict

dic = defaultdict(int)

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

top = bottom = ''
for _ in range(dic[')']):
    top += '('

for _ in range(dic['(']):
    bottom += ')'

print(top + s + bottom)

Solution (Python):
import bisect
import math
import sys
from collections import Counter, defaultdict, deque
from copy import copy, deepcopy
from heapq import heapify, heappop, heappush
from itertools import combinations, permutations
from queue import Queue

read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines 

def SI():
    return int(readline())
def MI():
    return map(int, readline().split())
def MLI():
    return map(int, open(0).read().split())

inf = float("inf")


def main():
    N = SI()
    S = input()
    
    left = 0
    right = 0
    for s in S:
        if s == '(':
            left += 1
        else:
            if left > 0:
                left -= 1
            else:
                right += 1
    ret = '(' * right + S + ')' * left
    print(ret)

if __name__ == "__main__":
    main()

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

L,R=0,0
l,r=0,0

for i in S:
    if i=="(":l +=1
    else:l -=1;L=min(L,l)

for i in S[::-1]:
    if i==")":r +=1
    else:r -=1;R=min(R,r)

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

Solution (Python):

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

l=0
r=0
pl=0
pr=0


for i in range(N):
    if S[i]==")":
        r+=1
        if pl+l<r:
            pl+=1
        else:
            pr-=1
    else:
        l+=1
        pr+=1

sl=["(" for i in range(pl)]
sr=[")" for i in range(pr)]

ans=sl + S + sr

print("".join(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 functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

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


def main():
    N = INT()
    S = INPUT()

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

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


if __name__ == '__main__':
    main()

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

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

for i in range(N):
    if S[i] == '(':
        S_number.append(1)
    else:
        S_number.append(-1)


for i in range(N):
    if S_number[i] == 1:
        for j in range(i, N):
            if S_number[j] == -1:
                S_number[i] = 0
                S_number[j] = 0
                break
            if j == N-1:
                S_number[i] = 0
                S.append(')')
    

insert_times = abs(sum(S_number))
for _ in range(insert_times):
    S.insert(0, '(')

answer = ''.join(S)
print(answer)

Solution (Python):
n = int(input())
s = input()
t = s
counter = 0  



before = ""
i = 0
while i < n:
    if s[i] == "(":
        if i > 0 and before == ")":
            if counter < 0:
                t = "(" * (-counter) + t
                counter = 0
        counter += 1
        before = "("
    else:
        counter -= 1
        before = ")"
    i += 1
if counter > 0:
    t += ")" * (counter)
elif counter < 0:
    t = "(" * (-counter) + t
print(t)

Solution (Python):
N = int(input())
S = input()
left_cnt = 0
right_cnt = 0
for c in S:
    if '(' == c:
        left_cnt += 1
    elif left_cnt == 0:
        right_cnt += 1
    else:
        left_cnt -= 1

print('(' * right_cnt + S + ')' * left_cnt)

Solution (Python):
def solve(n, s):
    counts = [0, 0]
    for l in s:
        if l == ')':
            if counts[0] > 0:
                counts[0] -= 1
            else:
                counts[1] += 1
        if l == '(':
            counts[0] += 1
    return '(' * counts[1] + s + ')' * counts[0]

_n = int(input())
_s = input()
print(solve(_n, _s))

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def roundUp(a, b):
        return -(-a // b)

    @staticmethod
    def toUpperMultiple(a, x):
        return Math.roundUp(a, x) * x

    @staticmethod
    def toLowerMultiple(a, x):
        return (a // x) * x

    @staticmethod
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

    @staticmethod
    def sign(n):
        if n == 0:
            return 0
        if n < 0:
            return -1
        return 1

    @staticmethod
    def isPrime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


MOD = int(1e09) + 7
INF = int(1e15)


def main():
    
    N = Scanner.int()
    S = Scanner.string()
    c1, c2 = 0, 0
    for i in range(N):
        if S[i] == ")":
            c1 -= 1
        else:
            c1 += 1
        if S[N-i-1] == ")":
            c2 += 1
        else:
            c2 -= 1
        c1 = max(0, c1)
        c2 = max(0, c2)
    ans = "(" * c2 + S + ")" * c1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
S = readline().decode("utf-8").rstrip()

left_cnt = 0
right_cnt = 0
for c in S:
    if '(' == c:
        left_cnt += 1
    elif left_cnt == 0:
        right_cnt += 1
    else:
        left_cnt -= 1

print('(' * right_cnt + S + ')' * left_cnt)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
S = readline().decode("utf-8").rstrip()

res = ""
left_cnt = 0
for c in S:
    if '(' == c:
        left_cnt += 1
        res += '('
    elif ')' == c:
        if left_cnt > 0:
            res += ')'
            left_cnt -= 1
        else:
            res = '(' + res + ')'
if left_cnt != 0:
    res += ")" * left_cnt

print(res)

Solution (Python):
n=int(input())
s=input()
l=[]
counter=0
for i in range(n):
    if s[i]=="(":
        counter+=1
    else:
        counter-=1
    l.append(counter)
suml=l[-1]
for i in range(n):
    if l[i]<0:
        s="("+s
        for j in range(n):
            l[j]+=1
        suml+=1
if suml>0:
    s+=")"*suml
print(s)

Solution (Python):
from itertools import accumulate
input()
S = input()
T = max(0, -min(accumulate(1 if s == "(" else -1 for s in S)))
U = max(0, -min(accumulate(1 if s == ")" else -1 for s in S[::-1])))
print("("*T + S + ")"*U)

Solution (Python):
from itertools import groupby

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

cnt_l = 0
cnt_r = 0
ans = ''
for key, elems in groupby(S):
    elems = list(elems)
    if key == '(':
        cnt_l += len(elems)
        ans += '(' * len(elems)
    else:
        cnt_r += len(elems)
        ans += ')' * len(elems)
        if cnt_l < cnt_r:
            ans = '(' * (cnt_r - cnt_l) + ans
            cnt_l += (cnt_r - cnt_l)

print(ans + ')' * (cnt_l - cnt_r))

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

d = [0] * N
if S[0] == "(":
    d[0] = 1
else:
    d[0] = -1
for i in range(1,N):
    d[i] = d[i-1]
    if S[i] == "(":
        d[i] += 1
    else:
        d[i] -= 1
        
x = max(-min(d), 0)
S = "(" * x + S + ")" * (d[N-1] + x)
print(S)

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

cr = 0
cl = 0

for i in s:
  if i == "(":
    cr += 1
  else:
    if cr > 0:
      cr -= 1
    else :
      cl += 1

print("("*cl+S+")"*cr)

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

cr = 0
cl = 0

for i in s:
  if i == "(":
    cr += 1
  else:
    if cr > 0:
      cr -= 1
    else :
      cl += 1

print("("*cl+S+")"*cr)

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

add_left, cash = 0, 0
for p in s:
    if cash == 0 and p == ")":
        add_left += 1
    elif p == "(":
        cash += 1
    else:
        cash -= 1

add_right, cash = 0, 0
for p in s[::-1]:
    if cash == 0 and p == "(":
        add_right += 1
    elif p == ")":
        cash += 1
    else:
        cash -= 1

print(add_left * "(" + s + add_right * ")")

Solution (Python):
N = int(input())
S = input()
A = []
a = 0
l = r = 0
for s in S:
    if s == '(':
        if a >= 0:
            a += 1
        else:
            l -= a
            a = 1
    else:
        
        a -= 1
if a != 0:
    if a < 0:
        l -= a
    else:
        r += a



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

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

t = []
num = 0
for i in range(n):
    if num == 0 and s[i] == ')':
        t.insert(0, '(')
        t.append(')')
    else:
        t.append(s[i])
        if s[i] == '(':
            num += 1
        else:
            num -= 1

if num > 0:
    for i in range(num):
        t.append(')')

for i in t:
    print(i, end='')

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

cr = 0
cl = 0

for i in range(N):
    if S[i] == '(':
        cr += 1
    else:
        if cr > 0:
            cr -= 1
        else:
            cl += 1
print('('*cl+S+')'*cr)

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

tmp = 0
a = 0
for i in s:
    if i == "(":
        tmp -= 1
    else:
        tmp += 1
    a = max(a, tmp)
ans = a * "(" + s
print(ans + ")" * (ans.count("(") - ans.count(")")))

Solution (Python):
n = int(input())
s = input()
t = s
s += "("
cnt = 0
for i in range(n):
  if s[i] == "(":
    cnt -= 1
  else:
    cnt += 1
  if s[i] == ")" and s[i+1] == "(":
    if cnt > 0:
      t = "("*cnt + t
      cnt = 0
if cnt < 0:
  t += ")"*(-cnt)
print(t)

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

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

for i in range(N):
    if S[i] == '(':
        S_number.append(1)
    else:
        S_number.append(-1)


for i in range(N):
    if S_number[i] == 1:
        for j in range(i, N):
            if S_number[j] == -1:
                S_number[i] = 0
                S_number[j] = 0
                break
            if j == N-1:
                S_number[i] = 0
                S.append(')')
    

insert_times = abs(sum(S_number))
for _ in range(insert_times):
    S.insert(0, '(')

answer = ''.join(S)
print(answer)

Solution (Python):
import numpy as np
import copy

N= int(input())
S=input()
SS= copy.copy(S)
S = list(S)


flag = 1

while flag == 1:
    flag = 0
    flag2 = 1
    i = 0
    while flag2 and len(S)>1:
    
        
        if S[i]=="(" and S[i+1] ==")":
            
            flag = 1
            del S[i] 
            del S[i]
            i -= 1
            
        i += 1
        i = max(0,i)
        if i+1>=len(S):
            flag2 = 0
a=0
b=0
for i in range(len(S)):
    if S[i]=="(":
        b+=1
    elif S[i]==")":
        a+=1


A = ""
B = ""


for x in range(a):
    
    A += "("   
for x in range(b):    
    B += ")"   

        

print(A+SS+B)

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

while True:
    if tmp.count("()") == 0:
        break
    tmp = "".join(tmp.split("()"))

x = 0
y = 0
for c in tmp:
    if c == ")":
        x += 1
    else:
        y += 1

ans = "("*x + s + ")"*y
print(ans)

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

l = "("
r = ")"

t = 0
k = 0
ma = 0
for i in range(N):
  if S[i] == r:
    t += 1
  else:
    k += 1
  ma = max(ma, t - k)

A = [l] * ma + S + [r] * (ma + k - t)

print("".join(A))