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

s=s[::-1]
balance = 0
i = 0
while i < len(s):
    if s[i] == ')':
        balance+=1
    else:
        balance-=1
    if balance<0:
        s.insert(0, ')')
        balance+=1
        i+=1
    i+=1


balance = 0
i = 0
s=s[::-1]
while i < len(s):
    if s[i] == '(':
        balance+=1
    else:
        balance-=1
    if balance<0:
        s.insert(0, '(')
        balance+=1
        i+=1
    i+=1

print(''.join(s))

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

def add1(S):
  cum=[0]
  for i in range(len(S)):
    if S[i]=='(':cum.append(cum[-1]+1)
    else:cum.append(cum[-1]-1)
  if min(cum)>=0:return S
  out = '('*(-min(cum))
  out += S
  return out

def add2(S):
  cum=[0]
  for i in range(len(S)):
    if S[i]=='(':cum.append(cum[-1]+1)
    else:cum.append(cum[-1]-1)
      
  if cum[-1]==0:return S
  n = cum[-1]
  out = S + ')'*n
  return out

S = add1(S)
S = add2(S)
print(S)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)

def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

from collections import deque





def solve():
    N = II()
    S = LS()
    q = deque([])
    
    cnt = 0
    for s in S:
        if s == '(':
            cnt += 1
            q.append(s)
        else:   
            if cnt >= 1:
                q.append(s)
                cnt -= 1
            else:
                q.appendleft('(')
                q.append(s)
    for _ in range(cnt):
        q.append(')')

    
    printlist(q, '')

if __name__ == '__main__':
    solve()

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

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

if __name__ == "__main__":
    main()

Solution (Python):
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().strip()

def main():
    N = int(input())
    S = input()
    height = 0
    deepest = 0
    for c in S:
        if c == '(':
            height += 1
        else:
            height -= 1
        deepest = min(deepest, height)
    ans = '(' * (-deepest) + S + ')' * (height - deepest)
    print(ans)

if __name__ == "__main__":
    main()

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

l = 0
for i in range(n):
    ans += s[i]
    if s[i] == ")":
        if l == 0:
            ans = "(" + ans
        else:
            l -= 1
    else:
        l += 1

ans += (")"*l)

print(ans)

Solution (Python):
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import chain
def main():
    n = int(input())
    s = tuple(input())
    cnt = 0
    cnt_ushiro = 0
    cnt_mae = 0
    for se in s:
        cnt += se == ')'
        cnt -= se == '('
        cnt_mae = max(cnt_mae, cnt)
    cnt -= cnt_mae
    if cnt < 0:
        cnt_ushiro = -cnt
    s_mae = ('(') * cnt_mae
    s_ushiro = (')') * cnt_ushiro
    r = tuple(chain(s_mae, s, s_ushiro))
    print(*r,sep="")

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
s = list(input())
d = [0]
x = 0

for i in range(len(s)):
    if s[i] == '(':
        x += 1
    else:
        x -= 1
    d.append(x)

ans = []
x = min(d)

for i in range(max(0,(-1*x))):
    ans.append('(')

for i in s:
    ans.append(i)

for i in range(max(d[len(d)-1]-x,0)):
    ans.append(')')

a = ''.join(ans)

print(a)

Solution (Python):
import re

N = int(input())
s = input()[:N]
s_check = s
s_check = re.sub('\(\)', '', s_check)

while len(s_check) > 0:
    for i in range(len(s_check)):
        if s_check[i] == ')':
            s = '(' + s
            s_check = '(' + s_check
            break
        elif s_check[i] == '(':
            break

    for i in range(len(s_check)):
        if s_check[-i-1] == '(':
            s = s + ')'
            s_check = s_check + ')'
            break
        elif s_check[-i-1] == ')':
            break

    s_check = re.sub('\(\)', '', s_check)

print(s)

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


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    rank = 0
    q = deque()
    for s in S:
        if rank == 0:
            if s == ")":
                q.appendleft("(")
                q.append(")")
            else:
                q.append("(")
                rank += 1
        else:
            if s == ")":
                q.append(")")
                rank -= 1
            else:
                q.append("(")
                rank += 1
    while rank > 0:
        q.append(")")
        rank -= 1
    return "".join(q)


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))

Solution (Python):
import copy
N = int(input())
S = list(input())
S_ans = copy.deepcopy(S)
app = 0
q = [0]
save = 0
for i in range(N):
    if S[i] == '(':
        q.append(q[-1] + 1)
        
    else:
        q.append(q[-1] - 1)
        if q[-1] == -1:
            S_ans.insert(app + save,"(")
            app += 1
            q[-1] = 0

for i in range(q[-1]):
    S_ans.append(")")
print("".join(S_ans))

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

stack = []
for c in S:
    if len(stack) > 0:
        last = stack[-1]
        if last == '(' and c == ')':
            stack = stack[:-1]
            continue
    stack.append(c)

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

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

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


x = 0
y = 0
for i in range(n):
    if s[i] == '(':
        x += 1

    if s[i] == ')':
        if x >= 1:
            x -= 1
        else:
            y += 1

for _ in range(x):
    s.append(')')

for _ in range(y):
    s.insert(0,'(')
ans = ''.join(s)
print(ans)

Solution (Python):
N = int(input())
S = input()
nS = S
for i in range(50):
    nS = nS.replace("()", "")
r = nS.count(")")
l = nS.count("(")
print("(" * r + S + ")" * l)

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

while s_.count('()'):
    s_ = s_.replace('()', '')

l = s_.count(')')
r = len(s_) - l

ans = '(' * l + s + ')' * r
print(ans)

Solution (Python):
def main():
    import sys

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

    n = int(input())
    s = input()
    cnt = 0
    m = 0
    for i in range(n):
        if s[i] == '(':
            cnt += 1
        else:
            cnt -= 1
        m = min(m, cnt)
    ans = '('*(-m)+s+')'*(cnt-m)
    print(ans)


if __name__ == '__main__':
    main()

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

Solution (Python):
n = int(input())
s = input()
while True:
  c = 0
  for i in range(len(s)):
    if s[i] == "(":
      c += 1
    else:
      c -= 1
    if c < 0:
      s = "(" + s
      break
  if c > 0:
    s = s + ")"
  if c == 0:
    print(s)
    break

Solution (Python):
from collections import deque

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


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

for _ in range(left):
    s.append(")")
    

for _ in range(right):
    s.appendleft("(")

print("".join(s))

Solution (Python):
from collections import deque

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


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

for _ in range(left):
    s.append(")")
    

for _ in range(right):
    s.appendleft("(")

print("".join(s))

Solution (Python):
from collections import deque

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

reserveL = deque()
out = deque()
q = deque()

for s in S:
    if s == "(":
        reserveL.append(s)
        out.append("(")
    else:
        
        if len(reserveL) == 0:
            out.appendleft("(")
            out.append(")")
        else:
            out.append(")")
            reserveL.popleft()

    


while reserveL:
    out.append(")")
    reserveL.popleft()
ans = ""
while out:
    ans += out.popleft()
print(ans)

Solution (Python):
from collections import deque

N = int(input())
S = input()
que = deque(S)
l = r = 0

for s in S:
    if s == '(':
        l += 1
    else:
        r += 1
    if l < r:
        que.appendleft('(')
        l += 1
else:
    ans = "".join(que)
    if r < l:
        ans = ans + ")" * (l - r)
print(ans)

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

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

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

    return


if __name__ == '__main__':
    main()

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

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

if __name__ == "__main__":
    main()

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

lp=0
rp=0
for i in range(n):
  if s[i]=='(':
    rp+=1
  else:
    rp=rp-min(rp,1)
for i in range(n-1,-1,-1):
  if s[i]==')':
    lp+=1
  else:
    lp=lp-min(lp,1)

print('('*max(0,lp)+s+max(0,rp)*')')

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

n = int(input())
S = input().rstrip()
b = 0
q = 0

for s in S:
    if s == '(':
        b +=1
    else:
        if b>0:
            b -= 1
        else:
            q += 1
print('('*q+S+')'*b)

Solution (Python):
n=int(input())
s=input()
ans=[]
minscore=0
score=0
for i in range(n):
  if s[i]=='(':
    score+=1
  else:
    score-=1
  minscore=min(minscore,score)
finalscore=score
for i in range(-minscore):
  ans.append('(')
for i in range(n):
  ans.append(s[i])
for i in range(-minscore+finalscore):
  ans.append(')')
print(''.join(ans))

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

flg_l = False
cnt_r = 0
cnt_l = 0

for i in range(N):
    if(S[i] == "("):
        cnt_r += 1
        flg_l = True            
    else:
        if(flg_l):
            if(cnt_r > 0):
                cnt_r -= 1
            else:
                cnt_l += 1
                flg_l = False
        else:
            cnt_l += 1
    
ans = ""

ans += ("("*cnt_l)+S+(")"*cnt_r)
print(ans)

Solution (Python):
n,s = open(0).read().split()

imp_close = 0
imp_open = 0

for char in s:
    if char == '(':
        imp_open += 1
    else:
        if imp_open:
            imp_open -= 1
        else:
            imp_close += 1

print('('*imp_close + s + ')'*imp_open)

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

num = [0]
for c in s:
    if c == '(':
        num.append(num[-1] + 1)
    else:
        num.append(num[-1] - 1)

for _ in range(num[0] - min(num)):
    print('(', end='')

print(s, end='')

for _ in range(num[-1] - min(num)):
    print(')', end='')

Solution (Python):
N = input()
S = input()
s = S
for i in range(50):
  S = S.replace('()','')
l = S.count(')')
r = S.count('(')
print('('*l+s+')'*r)

Solution (Python):

"""
@author: H_Hoshigi
"""
def main():
    N = int(input())
    S = input()

    solo_close_no = 0
    for i in range(N):
        if S[-i-1] == ")":
            solo_close_no += 1
        elif solo_close_no >= 1:
            solo_close_no -= 1
    
    solo_open_no = 0
    for i in range(N):
        if S[i] == "(":
            solo_open_no += 1
        elif solo_open_no >= 1:
            solo_open_no -= 1

    answer = "("*solo_close_no + S + ")"*solo_open_no
    print(answer)

if __name__ == "__main__":
    main()

Solution (Python):
import sys

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


def resolve():
    n = int(input())
    S = input()

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


if __name__ == '__main__':
    resolve()

Solution (Python):
n = int(input())
s = input()
from collections import deque
q = deque([])
cnt = 0
for i in range(n):
    if s[i]==')':
        if cnt >0:
            cnt-=1
        else:
            q.appendleft('(')
        q.append(')')
    else:
        q.append('(')
        cnt += 1
if cnt:
    for _ in range(cnt):
        q.append(')')
print(''.join(q))

Solution (Python):
import sys

input = sys.stdin.readline


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

    ans = ""
    n_left = 0
    n_right = 0
    for s in S:
        if s == "(":
            n_left += 1
        else:
            if n_left > 0:
                n_left -= 1
            else:
                n_right += 1

    ans = "".join(("(" * n_right, S, ")" * n_left))
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
S = input()
T = S.replace('()', '')
for _ in range(50):
  T = T.replace('()', '')
print('(' * T.count(')') + S + ')' * T.count('('))

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LS2(): return list(sys.stdin.readline().rstrip())  

N = I()
S = LS2()

a,b = 0,0
left = []
for i in range(N):
    if S[i] == '(':
        a += 1
    else:
        b += 1
    if a < b:
        a,b = 0,0
        left.append('(')

ANS = left + S + [')']*(a-b)

print(''.join(ANS))

Solution (Python):
N = int(input())
S = list(input())
L = 0
out = []
out2 = []
for i in range(N):
    X = S[i]
    if X=="(":
        L += 1
        out.append("(")
    elif X==")":
        if L>0:
            L += -1
            out.append(")")
        else:
            out2.append("(")
            out.append(")")
for i in range(L):
    out.append(")")
print("".join(out2)+"".join(out))

Solution (Python):
n = input()
s = input()
ss = s
for i in range(50):
  s = s.replace('()','')
l = s.count(')')
r = s.count('(')
print('('*l+ss+')'*r)

Solution (Python):
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
s = input()

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

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

s = '('*count + s
print(s)

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

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

dic = {'(':1, ')':-1}

rlt = ''
cnt = 0
for s in S:
  cnt += dic[s]
  rlt += s
  if cnt < 0:
    rlt = '(' + rlt
    cnt = 0
  
if cnt > 0:
  rlt += ')'*cnt
  
print(rlt)

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

l, r = 0, 0
p, m = 0, 0
for i in range(N):
  if S[i] == "(":
    l += 1
  else:
    r += 1
  if l < r:
    p += 1
    l += 1

m = l - r

for i in range(p):
  print("(", end = "")
print(S, end ="")
for i in range(m):
  print(")", end = "")

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

c0 = 0
c1 = 0
z0 = 0
z1 = 0
for i in range(n):
    if s[i] == "(":
        c0 += 1
    else:
        if c0 > 0:
            c0 -= 1
        else:
            c1 += 1
ans = ["("]*c1 + s + [")"]*c0
print("".join(ans))

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

c0 = 0
c1 = 0
z0 = 0
z1 = 0
for i in range(n):
    if s[i] == "(":
        c0 += 1
    else:
        if c0 > 0:
            c0 -= 1
        else:
            c1 += 1
z0 = c1
s = s[::-1]
c0 = 0
c1 = 0
for i in range(n):
    if s[i] == ")":
        c0 += 1
    else:
        if c0 > 0:
            c0 -= 1
        else:
            c1 += 1
z1 = c1
s = s[::-1]
ans = ["("]*z0 + s + [")"]*z1
print("".join(ans))

Solution (Python):
N=int(input())
S=input()
A=0 
B=0 

for s in S:
    if s=='(':
        A+=1
    elif s==')' and A>0:
        A-=1
    else:
        B+=1

print('('*B+S+')'*A)

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

a = ""

stack = []

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

while len(stack) > 0:
    if stack[len(stack) - 1] == ")":
        e = len(stack) - 1
        s = e
        while s - 1 >= 0 and stack[s - 1] == ")":
            s -= 1
        a = "(" * (e - s + 1) + a
        stack = stack[:s]
    elif stack[len(stack) - 1] == "(":
        e = len(stack) - 1
        s = e
        while s - 1 >= 0 and stack[s - 1] == "(":
            s -= 1
        a = a + ")" * (e - s + 1)
        stack = stack[:s]

print(a)

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

Solution (Python):
n = int(input())
S = input()
lc = 0
rc = 0
for s in S:
    if s=='(':
        rc += 1
    else:
        if rc:
            rc -= 1
        else:
            lc += 1
print('('*lc+S+')'*rc)

Solution (Python):
_,S,l,r=input(),input(),'(',')'
t=S
while t.count(l+r):
 t=t.replace(l+r,'')
print(l*t.count(r)+S+r*t.count(l))

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():

    N = in_n()
    S = in_s()

    ts = S
    while ts.count('()'):
        ts = ts.replace('()', '')

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


if __name__ == '__main__':
    main()

Solution (Python):
_ = input()
S = input()

needs_right = 0
needs_left = 0

for c in S:
    if c == '(':
        needs_right += 1
    else:
        if needs_right == 0:
            needs_left += 1
        else:
            needs_right -= 1

print('(' * needs_left + S + ')' * needs_right)

Solution (Python):
input()
s=t=input()
l,r=p='()'
exec("t=t.replace(p,'');"*50)
c=t.count
print(l*c(r)+s+r*c(l))

Solution (Python):
input();s=t=input();l,r=p='()'
exec("t=t.replace(p,'');"*50)
c=t.count;print(l*c(r)+s+r*c(l))

Solution (Python):
input();s=t=input();l,r=p='()'
exec("t=t.replace('()','');"*50)
c=t.count;print(l*c(r)+s+r*c(l))

Solution (Python):
input()
s=t=input()
l,r=p='()'
exec("t=t.replace('()','');"*50)
c=t.count
print(l*c(r)+s+r*c(l))

Solution (Python):
input();s=t=input()
while'()'in t:t=t.replace('()','')
c=t.count;print('('*c(')')+s+')'*c('('))

Solution (Python):
input()
s=t=input()
while '()' in t: t=t.replace('()','')
c=t.count
print('('*c(')')+s+')'*c('('))

Solution (Python):
_,s=input(),input()
t=0
for c in s:
  if c=='(': t+=1
  else: t-=1
  if t<0: s='('+s; t+=1
print(s+')'*t)

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

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    S = SS()

    stk = []
    ans = collections.deque()

    for i in S:
        if i == '(':
            stk.append(i)
        else:
            if stk and stk[-1] == '(':
                stk.pop()
            else:
                ans.appendleft('(')
        ans.append(i)
    
    while stk:
        ans.append(')')
        stk.pop()

    print(''.join(ans))

if __name__ == '__main__':
    resolve()

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    S = SS()

    stk = []
    ans = collections.deque()

    for i in S:
        if i == '(':
            stk.append(i)
            ans.append(i)
        else:
            if stk and stk[-1] == '(':
                stk.pop()
                ans.append(i)
            else:
                ans.appendleft('(')
                ans.append(i)
    
    while stk:
        ans.append(')')
        stk.pop()

    print(''.join(ans))

if __name__ == '__main__':
    resolve()

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    S = SS()

    stk = []
    ans = []

    for i in S:
        if i == '(':
            stk.append(i)
            ans.append(i)
        else:
            if stk and stk[-1] == '(':
                stk.pop()
                ans.append(i)
            else:
                ans.insert(0, '(')
                ans.append(i)
    
    while stk:
        ans.append(')')
        stk.pop()

    print(''.join(ans))

if __name__ == '__main__':
    resolve()

Solution (Python):
import math
import collections
import fractions
import itertools
import functools
import  operator

def solve():
    n = int(input())
    s = input()
    l, r = 0, 0
    for i in s:
        if i == "(":
            r += 1
        else:
            if r != 0:
                r -= 1
            else:
                l += 1
    ans = "("*l + s + ")"*r
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
N = int(input())
S = input().strip()
while True:
    lv = 0
    lmin = len(S)
    for i in range(len(S)):
        if S[i]=="(":
            lv += 1
        else:
            lv -= 1
        lmin = min(lmin,lv)
    if lmin<0:
        S = "("*(-lmin)+S
    else:break
lv = 0
for i in range(len(S)):
    if S[i]=="(":
        lv += 1
    else:
        lv -= 1

if lv>0:
    S = S+")"*lv
print(S)

Solution (Python):
n = int(input())
s = input()
ans = s
while s.count("()")>0:
    s = s.replace("()", "")
cnt_l = s.count(")")
cnt_r = s.count("(")
ans = cnt_l * "(" + ans
ans += cnt_r * ")"
print(ans)

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

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

Solution (Python):
N,S = open(0).read().split()
o = 0
c = 0
pre = 0
temp_o = 0
for b in S:
    if b == '(':
        o += 1
        temp_o += 1
    else:
        c += 1
        if temp_o == 0:
            pre += 1
        else:
            temp_o -= 1
suf = max(0,pre+o-c)
ans = ('('*pre) + S + (')'*suf)
print(ans)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(readline())
    s = input()

    l = 0
    r = 0

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


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
s = input()
writtenC = 0
writtenD = 0
for i in range(n):
    if s[i] == ")" and writtenC == 0:
        writtenD += 1
    elif s[i] == ")":
        writtenC -= 1
    else:
        writtenC += 1
print("(" * writtenD + s + ")"*writtenC)

Solution (Python):
N = int(input())
T = input()
S = list(T)
G = True
while G:
    G = False
    for i in range(1, len(S)):
        if S[i - 1] == '(' and S[i] == ')':
            S.pop(i)
            S.pop(i - 1)
            G = True
            break
for s in S:
    if s == '(':
        T = T + ')'
    else:
        T = '(' + T
print(T)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *



N = INT()
S = input()

l = 0
r = 0

for x in S:
	if x == "(":
		r += 1
	elif x == ")":
		if 0 < r:
			r -= 1
		else:
			l += 1

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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *



N = INT()
S = input()

l = 0
for x in S[::-1]:
	if x == ")":
		l += 1
	elif x == "(" and 0 < l:
		l -= 1
r = 0
for x in S:
	if x == "(":
		r += 1
	elif x == ")" and 0 < r:
		r -= 1

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

Solution (Python):



from fractions import gcd
from itertools import combinations,permutations,accumulate 

from collections import deque,defaultdict,Counter
import decimal
import re











import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
N = I()
S = input()
left = 0
right = 0
for i in range(N):
    if S[i] == '(':
        right += 1
    if S[i] == ')':
        if right >= 1:
            right -= 1
        else:
            left += 1
print('('*left + S + ')'*right)

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

d=[0]*n

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

x=min(d)

s='('*(-x) + s

d2=[0]*(len(s))
cnt=0
for i in range(len(s)):
    if s[i]=='(':
        cnt+=1
    else:
        cnt-=1
    d2[i]=cnt

s=s+')'*d2[-1]

print(s)

Solution (Python):
from collections import deque

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

ans = deque([])
emp = deque([])
for s in S[::-1]:
    if s == ")":
        ans.append('(')
    else:
        if ans:
            ans.pop()
        else:
            emp.append(')')
ans = list(ans)
emp = list(emp)
print("".join(ans)+S+"".join(emp))

Solution (Python):
import sys







def RD(): return sys.stdin.read()


def II(): return int(input())


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


def MF(): return map(float,input().split())


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


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))





def main():
	n=II()
	s=input()
	ss=s
	for _ in range(100):
		s=s.replace("()","")
	ans="("*s.count(")")+ss+")"*s.count("(")
	print(ans)
	
	
	





	

if __name__=="__main__":
	main()