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):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
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
from bisect import bisect
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
S = input()

T = S

while 1:
	if T.count("()") == 0:
		break
	try:
		T = T.replace("()", "")
	except:
		pass
l = 0
r = 0
for x in T:
	if x == ")":
		l += 1
	else:
		r += 1
print("("*l + S + ")"*r)

Solution (Python):
N = int(input())
S = input()
l, r = 0, 0
lp, rp = 0, 0

for i in range(N):
    if S[i] == '(':
        l += 1
    else:
        r += 1
    lp = max(lp, r-l)
rp = lp + l - r

ans = '(' * lp + S + ')' * rp
print(ans)

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

over = 0
ans_f = 0
ans_e = 0
for c in s:
    if c == "(":
        over += 1
    else:  
        if over > 0:
            over -= 1
        else:
            ans_f += 1

ans_e = over

ans = ("(" * ans_f) + s + (")" * ans_e)
print(ans)

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

over = 0
ans_f = 0
ans_e = 0
for c in s:
    if c == "(":
        over += 1
    else:  
        if over > 0:
            over -= 1
        else:
            ans_f += 1

ans_e = over

ans = ""
for i in range(0, ans_f):
    ans += "("

ans += s

for i in range(0, ans_e):
    ans += ")"

print(ans)

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

n=int(input())
s=list(input().strip())
from collections import deque
que=deque(s)
cnts=0
cntf=0
for i in range(n):
    if s[i]=="(" :
        cnts+=1
    if s[i]==")":
        if cnts==0:
            que.appendleft("(")
        else:
            cnts-=1
for i in range(cnts):
    que.append(")")
print("".join(que))

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

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


a=0
b=0
bb=0
for s in S:
    if s=="(":
        a+=1
    else:
        if a>0:
            a-=1
            b+=1
        else:
            bb+=1
for i in range(bb):
    S.insert(0,"(")
for i in range(a):
    S.append(")")
S="".join(S)
print(S)

Solution (Python):
n = int(input())
s = str(input())
right = 0
left  = 0
a = ""
for i in range(n):
    if s[i]=="(":
        right +=1
    else:
        if right > 0:
            right -=1
        else:
            a +="("
ans = a + s + ")"*right
print(ans)

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

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

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

Solution (Python):
N=int(input())
s=input()
ans = s
flag_A = True
r = 0
l = 0
while flag_A:
    flag_B =False
    for n,i in enumerate(s):
        if n != len(s)-1 and i =="(" and s[n+1] ==")":
            s = s[:n]+s[n+2:]
            flag_B = True
            break
    if not flag_B:
        flag_A = False
for i in s:
    if i ==")":
        r += 1
    else:
        l += 1
print("("*r+ans+")"*l)

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

d = [0]
o = c = 0
for i in range(N):
    if S[i] == '(':
        o += 1
    else:
        c += 1
    d.append(o - c)
x = min(d)
print('(' * -x + S + ')' * (d[-1] - x))

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

s = "".join(["("]*r+list(s)+[")"]*l)
  
print(s)

Solution (Python):
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))



N=one_int()
S=one_str()

head = 0
tail = 0

point=0
for a in S:
    if a =="(":
        point+=1
    else:
        point -=1
    if point<0:
        head += 1
        
        
        point += 1


print("("*head + S + abs(point)*")")

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

Solution (Python):
N = int(input())
S = input()
tmp = S[-1]
index = 0
ans = ''
cnt1 = 0
cnt2 = 0
for i in range(N):
    if S[i] == '(':
        cnt1 += 1
    elif cnt1 == 0:
        cnt2 += 1
    else:
        cnt1 -= 1

print('(' * cnt2 + S + ')' * cnt1)

Solution (Python):
n = int(input())
s = list(input())
validation = [False for _ in range(n)]

r = 0
l = 0
for i in range(n):
    if "(" == s[i]:
        r += 1
    else:
        if r > 0:
            r -= 1
        else:
            l += 1
print("(" * l + "".join(s) + ")" * r)

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

ans=''
b=0
for c in reversed(S):
    if c==')':
        b+=1
        ans=c+ans
    else:
        if b==0:
            ans=c+ans
            ans+=')'
        else:
            b-=1
            ans=c+ans
for _ in range(b):
    ans='('+ans
print(ans)

Solution (Python):


if __name__ == '__main__':
    N=int(input())
    S=input()
    r=0
    l=0

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

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
S = input()


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


ans = ('(' * lneed) + S + (')' * rneed)
print(ans)

Solution (Python):
n=int(input())
s=input()
t=s
l=str()
r=str()
while '()' in t:
  t=t.replace('()','')
if len(t)==0:
  print(s)
else:
  for i in range(len(t)):
    if t[i]=='(':
      r+=')'
    else:
      l+='('
  print(l+s+r)

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input().strip())
s = input().strip()
cnt = 0
pre = ''
for ss in s:
    if ss == '(':
        cnt += 1
    elif ss == ')':
        cnt -= 1
        if cnt < 0:
            pre += '('
            cnt += 1
else:
    post = ')' * cnt
print(pre + s + post)

Solution (Python):
N = int(input())
S = input()
x = 0
cnt = 0
for i in range(N):
    if S[i] == "(":
        cnt += 1
    else:
        cnt -= 1
    x = min(x, cnt)

    if i == N-1:
        d = cnt

S = "("*(-x) + S + ")"*(d+(-x))
print(S)

Solution (Python):
from collections import deque
n=int(input())
s = input()
cnt = [0]
ans = deque(list(s))
for i in range(n):
  if s[i]=="(":
    cnt.append(cnt[-1]+1)
  else:
    cnt.append(cnt[-1]-1)
rt = min(cnt)
if rt<0:
  ans.extendleft("("*(-rt))
if cnt[-1]-rt>0:
  ans.extend(")"*(cnt[-1]-rt))
print(*ans,sep="")

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

A1, A2 = [0 for _ in range(N)], [0 for _ in range(N)]
for i, s in enumerate(S):
  if i == 0:
    if s == '(': A1[i] = 1
    else: A2[i] = 1
  else:
    if s == '(':
      A1[i] = A1[i-1] + 1
      A2[i] = A2[i-1] 
    else:
      A1[i] = A1[i-1] 
      A2[i] = A2[i-1] + 1

A3, A4 = [0 for _ in range(N)], [0 for _ in range(N)]
for i in range(N-1, -1, -1):
  if i == N-1:
    if S[i] == '(': A3[i] = 1
    else: A4[i] = 1
  else:
    if S[i] == '(':
      A3[i] = A3[i+1] + 1
      A4[i] = A4[i+1] 
    else:
      A3[i] = A3[i+1] 
      A4[i] = A4[i+1] + 1

v1 = max(max([a2-a1 for a1, a2 in zip(A1,A2)]),0)
v2 = max(max([a3-a4 for a3, a4 in zip(A3,A4)]),0)
print('('*v1+S+')'*v2)

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

def main():
  left=0
  right=0
  for char in s:
    if char=="(":
      right+=1
    else:
      if right>0:
        right-=1
      else:
        left+=1
  return (left,right)
      

l,r=main()
print("("*l+s+r*")")

Solution (Python):
import sys

n = int(sys.stdin.readline().rstrip())
s = sys.stdin.readline().rstrip()

def main():
    l = r = 0
    for char in s:
        if char == '(':
            r += 1
        elif char == ')':
            if r:
                r -= 1
            else:
                l += 1

    return '(' * l + s + ')' * r

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

Solution (Python):

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

hazimekakko = 0
owarikakko = 0
sa = -1
for i in range(len(S)):
    if S[i] == "(":
        hazimekakko += 1
    else:
        owarikakko += 1
    sa = max(sa, owarikakko-hazimekakko)

S = sa*"(" + S

hazimekakko = 0
owarikakko = 0
for i in range(len(S)):
    if S[i] == "(":
        hazimekakko += 1
    else:
        owarikakko += 1
print(S + ")"*(hazimekakko-owarikakko))

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

    left = 0
    right = 0
    t = 0
    for c in list(S):
        if c == '(':
            t += 1
        if c == ')':
            if t > 0:
                t -= 1
            else:
                left += 1
    right = t
    print('(' * left + S + right * ')')


m()

Solution (Python):
N = int(input())
S = input()
c, d = 0, 0
for i in range(N):
  if S[i] == '(':
    c += 1
  elif S[i] == ')' and c > 0:
    c -= 1
  if S[N-i-1] == ')':
    d += 1
  elif S[N-i-1] == '(' and d > 0:
    d -= 1
print(d*'(' + S[:] + c*')')

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

right = 0
p = 0
left = 0
for s in sl:
    if s == "(":
        p -= 1
    else:
        p += 1
        left += 1
        right = max(p, right)

x = right + n - 2*left
print("("*right + ss + ")"*x)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    n=int(input())
    s=input()
    now=0
    l=0
    for c in s:
        if c=="(":
            now+=1
        else:
            now-=1
        if now==-1:
            l+=1
            now=0
    ans="("*l+s+")"*now
    print(ans)
main()

Solution (Python):


ans = 0  
N = int(input())
S = input()
hazimekakko = 0
owarikakko = 0
for i in range(N):
    if S[i] == "(":
        hazimekakko += 1
    else:
        owarikakko += 1
    ans = max(ans, owarikakko-hazimekakko)

S = abs(ans)*"(" + S

hazimekakko = 0
owarikakko = 0
for i in range(len(S)):
    if S[i] == "(":
        hazimekakko += 1
    else:
        owarikakko += 1

S = S + (hazimekakko-owarikakko)*")"
print(S)

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

d = S
while d.count('()')!=0:
	d = d.replace('()','')

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

z = '('*r + S + ')'*l

print(z)

Solution (Python):
N=int(input())
S=input()
a=[0]
for c in S:
    a.append(a[-1]+(1 if c=='(' else -1))
k=-min(a)
l=S.count('(')+k-S.count(')')
ans='('*k+S+')'*l

print(ans)

Solution (Python):

n=int(input())
s=input()
ss=s
l_cnt=0
r_cnt=0
if s.count('()')>0:
    
    while ss.count('()')>0:
        ss=ss.replace('()','')
    l_cnt=ss.count('(')
    r_cnt=ss.count(')')
    s+=')'*l_cnt
    s='('*r_cnt+s

    print(s)
else:
    l_cnt=s.count('(')
    r_cnt=s.count(')')
    s+=')'*l_cnt
    s='('*r_cnt+s
    print(s)

Solution (Python):
n = int(input())
s = input()
c1 = 0
c2 = 0
c = 0
for i in s:
    if i == '(':
        c1 += 1
    else:
        c2 += 1
        if c1+c< c2:
            c += 1
print('('*c + s + ')'*(c+c1-c2))

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

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

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

Solution (Python):
N = int(input())
s = input()
stack = []
a = 0
b = 0
for i in range(N):
  if stack and stack[-1] == "(" and s[i] == ")":
    stack.pop()
    a -= 1
  else:
    stack.append(s[i])
    if s[i] == "(":
      a += 1
    else:
      b += 1

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

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

print('('*unpaired_close + S + ')'*unpaired_open)

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

def I():
    return int(input())
def MI():
    return map(int,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 GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase


input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n=I()
s=input()
c=0
mm=0
for i in s:
    if i=='(':
        c+=1
    else:
        c-=1
    mm=min(mm,c)

print('('*-mm+s+')'*(c-mm))

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

q = deque()
for s in arg:
    if len(q) == 0:
        q.append(s)
    else:
        if q[-1] == '(' and s == ')':
            q.pop()
        else:
            q.append(s)
l = 0
r = 0
for i in range(len(q)):
    st = q.pop()
    if st == '(':
        r += 1
    else:
        l += 1
print('(' * l + arg + ')' * r)

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

count = 0
for i in s:
    if i == ")":
        count += 1
    else:
        s = "(" * count + s
        if count > 0:
            count = -1
        else:
            count -= 1

if count > 0:
    s = "(" * count + s
elif count < 0:
    s = s + ")" * -count

print(s)

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






c=0
m=0
for i in s:
    if i==")":
        c-=1
    else:
        c+=1
    m=min(m,c)
s=abs(m)*"("+s
l=s.count("(")
k=s.count(")")

if k-l>0:
    print((k-l)*"("+s)
else:
    print(s+(l-k)*")")

Solution (Python):
N = int(input())
S = input()
tmp = ""
for letter in S:
    if tmp == "":
        tmp += letter
    elif letter == ")" and tmp[-1] == "(":
        tmp = tmp[:-1]
    else:
        tmp += letter

head = "(" * tmp.count(")")
tail = ")" * tmp.count("(")
print(head + S + tail)

Solution (Python):


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

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

ans = "(" * s.count(")") + S + ")" * s.count("(")
print(ans)

Solution (Python):
from collections import Counter
n = int(input())
s = input()
cnt = 0
_max = 0
for _s in s[::-1]:
    if _s == ")":
        cnt -= 1
    else:
        cnt += 1
    _max = max(cnt, _max)
s += ")" * _max

cnt = 0
_max = 0
for _s in s:
    if _s == "(":
        cnt -= 1
    else:
        cnt += 1
    _max = max(cnt, _max)
s = "(" * _max + s
ct = Counter(s)

if ct.get("(") is None:
    ct["("] = 0
if ct.get(")") is None:
    ct[")"] = 0
if ct[")"] > ct["("]:
    s = "(" * (ct[")"] - ct["("]) + s
else:
    s = s + ")" * (ct["("] - ct[")"])
print(s)

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

cnt2=0
for i in range(n-1,-1,-1):
    if s[i]==")":
        cnt2+=1
    else:
        if cnt2>0:
            cnt2-=1
        else:
            pass

print(cnt2*"("+s+cnt1*")")

Solution (Python):


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

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

ans = "(" * s.count(")") + S + ")" * s.count("(")
print(ans)

Solution (Python):
N = int(input())
S = input()
ary = []
if S[0] == '(':
    ary.append(1)
else:
    ary.append(0)
    ary.append(1)
for i in range(1, N):
    if S[i-1] == S[i]:
        ary[-1] += 1
    else:
        ary.append(1)
if len(ary) % 2:
    ary.append(0)
c = [0, 0]
for i in range(0, len(ary), 2):
    c[0] += ary[i]
    c[1] += ary[i+1]
    if c[0] < c[1]:
        ary[0] += c[1]-c[0]
        c[0] = c[1]
if c[0] > c[1]:
    ary[-1] += c[0]-c[1]
ans = ''
for i, n in enumerate(ary):
    if i % 2 == 0:
        ans += '('*n
    else:
        ans += ')'*n
print(ans)

Solution (Python):

import sys


def solve(N: int, S: str):
    stack = []
    for i in range(N):
        if not stack:
            stack.append(S[i])
            continue

        if S[i] == "(":
            stack.append(S[i])
        else: 
            if stack[-1] == "(":
                stack.pop()
            else:
                stack.append(S[i])
    right_count = stack.count('(')
    left_count = stack.count(')')

    answer = '('*left_count+S+')'*right_count
    print(answer)
    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):
N = int(input())
S = input()
s = 0
mi = 0
for i in range(N):
    s += 1 if S[i] == "(" else -1
    mi = min(mi, s)
if s > 0:
    print(-mi * "(" + S + ")" * (s-mi))
else:
    print("(" * max(-s, -mi) + S + ")" * (max(-s, -mi) + s))

Solution (Python):
N=int(input())
S=input()
sl=list(S)
change=[0]
for i in range(1,N):
  if (sl[i-1]==')')and(sl[i]=='('):
    change.append(i)

change.append(N)
r_add=0
l_add=0
for i in range(len(change)-1):
  A=sl[change[i]:change[i+1]]
  r=0
  l=0
  for a in A:
    if a=='(':
      l+=1
    else:
      r+=1
      
  if r==l:
    continue
  elif r>l:
    if r_add>0:
      if r_add>=r-l:
        r_add-=r-l
      else:
        l_add+=r-l-r_add
        r_add=0
        
    else:
      l_add+=r-l
      
  else:
    r_add+=l-r
      
print('('*l_add+S+')'*r_add)

Solution (Python):
N = int(input())
S = input()
stack = []
for i in S:
    if len(stack) == 0:
        stack.append(i)
    else:
        prev = stack.pop()
        if prev == "(" and i == ")":
            continue
        else:
            stack.append(prev)
            stack.append(i)
ans = S
for i in stack:
    if i == ")":
        ans = "(" + ans
    else:
        ans = ans + ")"
print(ans)

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

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

m = min(a)
if m < 0:
    ans = -m * '(' + s
    last = -m + a[-1]
else:
    ans = s
    last = a[-1]
if last > 0:
    ans += ')' * last
print(ans)

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

m = 0
min_m = 0

for c in S:
    if c == '(':
        m += 1
    else:
        m -= 1
    min_m = min(min_m, m)

ans = '('*(-min_m) + S + ')'*(m-min_m)
print(ans)

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

    left = 0
    right = 0
    for s in S:
        if s == '(':
            right += 1
        else:
            if right <= 0:
                left += 1
            else:
                right -= 1

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


if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy


from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])
def graph():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=inpm()
        a-=1
        b-=1
        g[a].append(b)
        g[b].append(a)
    return n,m,g
 
def main():
    n=inp()
    s=input()
    r,l=0,0
    ans=[]
    for i in range(n):
        if s[i]=='(':
            r+=1
        elif s[i]==')':
            if r==0:
                l+=1
            else:
                r-=1
    for i in range(l):
        ans.append('(')
    for i in range(n):
        ans.append(s[i])
    for i in range(r):
        ans.append(')')
    print(''.join(ans))


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    N = int(input())
    S = input()
    left = 0
    right = 0
    stack = []
    for s in S:
        if s == "(":
            stack.append(s)
        else:
            if stack:
                stack.pop()
            else:
                left += 1
    right = len(stack)
    print("("*left + S + ")"*right)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N = int(input())
    S = input()
    left = 0
    right = 0
    stack = []
    for s in S:
        if s == "(":
            stack.append(s)
        else:
            if stack:
                stack.pop()
            else:
                left += 1
    right = len(stack)
    print("("*left + S + ")"*right)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

n = int(input())
s = input()
lCnt = 0
rCnt = 0
stack = deque()
stack.append(s[0])

for i in range(1, len(s)):

    if len(stack) == 0:
        stack.append(s[i])
        continue

    prev = stack.pop()

    if prev == '(' and s[i] == ')':
        continue
    else:
        stack.append(prev)
        stack.append(s[i])



for i in range(len(stack)):
    if stack[i] == '(':
        lCnt += 1
    else:
        rCnt += 1

s += ')' * lCnt
s = '(' * rCnt + s

print(s)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    S=input()
    a=0
    b=0

    for i in range(n):
        if(S[i]=='('):
            a+=1
        else:
            if(a>0): a-=1
            else: b+=1
    P='('*b

    a=0
    b=0
    for i in range(n-1,-1,-1):
        if(S[i]==')'):
            a+=1
        else:
            if(a>0): a-=1
            else: b+=1
    Q=')'*b
    print(P+S+Q)
resolve()

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

c1 = 0 
c2 = 0 

for i in range(N-1, -1, -1):
    if S[i] == "(":
        c1 += 1
    else:
        c2 += 1
    if c1 > c2:
        S.append(")")
        c2 += 1
        
if c2 > c1:
    T = ["("]*(c2-c1)
    S = T + S
    
print("".join(S))

Solution (Python):

import math


N = input()
S = input()

if S[0] == ")" :
  S = "(" + S
if S[-1] == "(" :
  S = S + ")"

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

if r < l :
  for i in range(l-r) :
    S = "(" + S
elif r > l :
  for i in range(r-l) :
    S = S + ")"

nowS = S
endflag = 0
while endflag == 0 :
  S = nowS
  while (len(S) != 0) :
    S = S.replace("()", "")
    if "()" not in S :
      break
    
  if len(S) == 0 :
    print (nowS)
    endflag = 1
  else :
    nowS = "(" + nowS + ")"

Solution (Python):
import sys


def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    left, right = 0, 0
    for char in s:
        if char == '(':
            right += 1 
            
        elif char == ')':
            if right: 
                
                right -= 1
            else: 
                
                left += 1
    
    ans = '(' * left + s + ')' * right
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys


def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    left, right = 0, 0
    for char in s:
        if char == '(':
            right += 1 
            
        elif char == ')':
            if right: 
                
                right -= 1
            else: 
                left += 1
    
    ans = '(' * left + s + ')' * right
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys


def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    left, right = 0, 0
    for char in s:
        if char == '(':
            
            
            
                right += 1
        elif char == ')':
            if right:
                right -= 1
            else:
                left += 1
    
    ans = '(' * left + s + ')' * right
    print(ans)

            

if __name__ == "__main__":
    main()

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

def l(s):
    return s.count("(")

def r(s):
    return s.count(")")

prev = ""
while prev != s:
    prev = s
    pt = 0
    while True:
        
        if pt>=len(s):
            break
        char = s[pt]
        
        if char=="(" and l(s[pt+1:]) >= r(s[pt+1:]):
            s = s+")"
        if char==")" and l(s[:pt]) <= r(s[:pt]):
            s = "("+s
            pt+=1
        pt+=1

print(s)

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

l,cnt1=0,0
for s in S:
  if s=='(':
    cnt1+=1
  else:
    cnt1-=1
    l=min(l,cnt1)
r,cnt2=0,0
for s in S[::-1]:
  if s==')':
    cnt2+=1
  else:
    cnt2-=1
    r=min(r,cnt2)
print('('*-l+ S + ')'*-r)

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

l,cnt1=0,0
for s in S:
  if s=='(':
    cnt1+=1
  else:
    cnt1-=1
    l=min(l,cnt1)
r,cnt2=0,0
for s in S[::-1]:
  if s==')':
    cnt2+=1
  else:
    cnt2-=1
    r=min(r,cnt2)
print('('*-l+ S + ')'*-r)

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

print(ans)

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

stack = []
for c in s:
  
  if c == "(":
    stack.append(c)
    
  
  else:
    
    if not stack:
      d.appendleft('(')
      
    
    else:
      
      stack.pop()


while stack:
  stack.pop()
  d.append(')')
  
print("".join(list(d)))

Solution (Python):
import numpy as np

N = int(input())
S = list(input())
S2 = np.array([1 if x == ')' else -1 for x in S])
S_cum = S2.cumsum()
S = ['('] * S_cum.max() + S
left = S.count('(')
right = len(S) - left
if left > right:
    S = S + [')'] * (left-right)
elif right > left:
    S = ['('] * (right-left)
print(''.join(S))

Solution (Python):
def examD():
    N = I()
    St = S()
    cur = 0
    left = 0; right = 0
    for s in St:
        if s=="(":
            cur +=1
        if s==")":
            if cur>0:
                cur -=1
            else:
                left +=1
    right = cur
    ans = "("*left + St + ")"*right
    print(ans)

import sys
import copy
import bisect
import heapq
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

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

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

print(result)

Solution (Python):

n=int(input())
s=input()
count=1
Llist=[]
Rlist=[]
s=s+"X"
for i  in range(n):
    if s[i]==s[i+1]:
        count+=1
    else:
        if s[i]=="(":
            Llist.append(count)
        else:
            Rlist.append(count)
        count=1

if s[0]==")":
    Llist.insert(0,0)
if s[-2]=="(":
    Rlist.append(0)

Lsum=0
Rsum=0
for i in range(len(Llist)):
    Lsum+=Llist[i]
    Rsum+=Rlist[i]
    if Lsum>=Rsum:
        pass
    elif Lsum<Rsum:
        Llist[0]+=(Rsum-Lsum)
        Lsum+=(Rsum-Lsum)
if Lsum!=Rsum:
    Rlist[-1]+=(Lsum-Rsum)
anstr=""
for i in range(len(Llist)):
    a,b=Llist[i],Rlist[i]
    anstr+="("*a
    anstr+=")"*b
print(anstr)