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())
N = input()
L = 0
R = 0
num = 0
for c in N:
    if c == '(':
        num += 1
    else:
        if num:
            num -= 1
        else:
            L += 1
R = num
 
print('('*L+N+')'*R)

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

add_left=0
add_right=0
for s in S:
  if s=="(":
    add_right+=1
  elif add_right==0:
    add_left+=1
  else:
    add_right-=1

print('(' * add_left + S + ')' * add_right)

Solution (Python):
N = int(input())
S = input()
l = r = 0
L = ""
for i in S:
    if i == "(":
        l += 1
    else:
        r += 1
    if l < r:
        L += "("
        l += 1
R = ")"* (l-r)
print(L+S+R)

Solution (Python):
N = int(input())
motoS = input()
S = list(motoS)
start = 0
end = 0
for i in range(N):
    if S[i] == '(':
        end += 1
    else:
        end -= 1
    if end < 0:
        start += 1
        end = 0
print('('*start+motoS+')'*end)

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

now=0
sen=0

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

print("("*sen + s + ")"*now)

Solution (Python):
import sys
from collections import deque


def IN_I(): return int(sys.stdin.readline().rstrip())
def IN_LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def IN_S(): return sys.stdin.readline().rstrip()
def IN_LS(): return list(sys.stdin.readline().rstrip().split())


N = IN_I()
S = IN_S()
d = deque(S)

l = 0
for i in range(N):
    if S[i] == '(':
        l += 1
    else:
        if l == 0:
            d.appendleft('(')
        else:
            l -= 1

r = 0
for i in range(N - 1, -1, -1):
    if S[i] == ')':
        r += 1
    else:
        if r == 0:
            d.append(')')
        else:
            r -= 1
print(''.join(d))

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

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

x = min(d)

s = '('*(-x) + s + ')'*(d[n]-x)
print(s)

Solution (Python):
n = int(input())
s = input()
ss = s
while ss.count('()'):
    ss = ss.replace('()', '')
left, right = ss.count('('), ss.count(')')
print('(' * right + s + ')' * left)

Solution (Python):
n = int(input())
s = str(input())
l = []
left, right = 0, 0
for c in s:
    if c == ')':
        if l == []:
            left += 1
        else:
            l.pop()
    else:
        l.append(1)
right = len(l)
print('(' * left + s + ')' * right)

Solution (Python):
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():

    n = I()
    s = S()

    cnt = 0
    right = 0
    
    for char in s:
        if char == "(":
            cnt += 1
        else:
            if cnt == 0:
                right += 1
            else:
                cnt -= 1

    ans = "("*right + s + ")"*cnt

    print(ans) 
    

        


main()

Solution (Python):
n = int(input())
s = input()
R, L = 0, 0
for i in range(len(s)):
    if s[i] == '(':
        R += 1
    else:
        if R:
            R -= 1
        else:
            L += 1

print('('*L + s + ')'*R)

Solution (Python):
n = int(input())
s = input()
cnt, L = 0, 0
for i in range(len(s)):
    if s[i] == '(':
        cnt += 1
    else:
        cnt -= 1

    if cnt < 0:
        L = min(L, cnt)

ans = '('*abs(L) + s
R = ans.count('(') - ans.count(')')
ans += ')'*R

print(ans)

Solution (Python):
N = int(input())
S = input()
T = list(1 if c == "(" else -1 for c in S)
l, l_min = 0, 0
r, r_min = 0, 0
for i in range(N):
    l += T[i]
    l_min = min(l_min, l)
    r -= T[N - i - 1]
    r_min = min(r_min, r)
print("".join(["(" * -l_min, S, ")" * -r_min]))

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

ans = []
count = 0
addFlag = True
for i in range(N):
    if addFlag:
        if S[i] == ')':
            ans.append(')')
            ans.insert(0,'(')
        else:
            ans.append('(')
            count += 1
            addFlag = False
    else:
        if S[i] == '(':
            ans.append('(')
            count += 1
        else:
            ans.append(')')
            count -= 1
            if count == 0:
                addFlag = True

for _ in range(count):
    ans.append(')')

print(''.join(ans))

Solution (Python):



from math import gcd
from itertools import combinations,permutations,accumulate, product 

from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq














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


INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())
n = I()
S = input()
left = 0
right = 0
for i in range(n):
    if S[i] == '(':
        right += 1
    elif S[i] == ')':
        if right >= 1:
            right -=1
        else:
            left += 1
print('('*left + S + ')'*right)

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

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

Solution (Python):
n = int(input())
a = input()
cr = 0
cl = 0
ans = a
for i in range(n):
  if a[i] == "(":
    cl += 1
  elif a[i] == ")":
    cr += 1
  if cl == 0 and cr != 0:
    ans = "(" + ans
    cr -= 1
  if cl != 0 and cr != 0:
    if cr >= cl:
      cl, cr = 0,cr-cl
    else:
      cl, cr = cl-cr,0
if cl != 0:
  for i in range(cl):
    ans = ans+")"
print(ans)

Solution (Python):
n = input()
cnt = 0
S = input()
m = 0
for s in S:
    if s == "(":
        cnt += 1
    else:
        cnt -= 1
    m = min(m, cnt)

left = -min(0, m)
right = abs(cnt - m)
print("(" * left + S + ")" * right)

Solution (Python):
n = int(input())
s = str(input())
c = 0
from collections import deque
res = deque([])
for i in range(n):
    if s[i] =='(':
        c += 1
    else:
        c -= 1
    if c < 0:
        res.appendleft('(')
        c = 0
    res.append(s[i])
if c > 0:
    res.append(')'*c)
print(''.join(list(res)))

Solution (Python):
def main():
	N = int(input())
	S = input()
	brackets = [0, 0]
	for i in range(len(S)):
		if S[i] == ")":
			if brackets[0] > 0:
				brackets[0] -= 1
			else:
				brackets[1] += 1
		elif S[i] == "(":
			brackets[0] += 1
	print(brackets[1] * "(" + S + brackets[0] * ")")

main()

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

count = 0
new_left = 0
new_right = 0

for si in s:
    if si == '(':
        count += 1
    else:
        count -= 1

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

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

Solution (Python):
n = int(input())
s = input()
counter_l = 0
pairs = 0
double_check = set()

for i in range(n):
    if s[i] == "(":
        counter_l += 1
        for j in range(i + 1, n):
            if s[j] == ")" and j not in double_check:
                pairs += 1
                double_check.add(j)
                break
counter_r = n - counter_l
s = s + ")" * (counter_l - pairs)
s = "(" * (counter_r - pairs) + s

print(s)

Solution (Python):
n = int(input())
s = input()
cnt_l, cnt_r = 0, 0

for x in s:
	if x == "(":
		cnt_l += 1
	elif cnt_l > 0:
		cnt_l -= 1
	else:
		cnt_r += 1

print(cnt_r * "(" + s + cnt_l * ")")

Solution (Python):
n = int(input())
s = input()
cnt_l, cnt_r = 0, 0

for x in s:
	if x == "(":
		cnt_l += 1
	elif cnt_l > 0:
		cnt_l -= 1

for x in s[::-1]:
	if x == ")":
		cnt_r += 1
	elif cnt_r > 0:
		cnt_r -= 1

print(cnt_r * "(" + s + cnt_l * ")")

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

l = 0
r = 0
for si in s:
  if si == "(":
    r += 1
  else:
    if r == 0:
      l += 1
    else:
      r -= 1
ans = ""
for _ in range(l):
  ans += "("
ans += s
for _ in range(r):
  ans += ")"
print(ans)

Solution (Python):
n=int(input())
s=input()
mn=0
sm=0
for i in range(n):
  sm+=1 if s[i]=="(" else -1
  mn=min(mn,sm)
mn*=-1
print("("*mn+s+")"*(sm+mn))

Solution (Python):
def cin():  return list(map(int,input().split()))

N = cin()[0]
S = input()

tmp = S[::]
for i in range(100): tmp = tmp.replace("()", "")
cnt1 = 0
cnt2 = 0
for i in range(len(tmp)):
    if tmp[i] == '(': cnt1 += 1
    else: cnt2 += 1

ans = S[::]
ans = "(" * cnt2 + S + ')' * cnt1;
print(ans);

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

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

ans = "("*l + S + ")"*r

print(ans)

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

a=-m
b=x-m
print('('*a+S+')'*b)

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

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

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

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

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

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

Solution (Python):
import math
from typing import List, Any


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> Any:
    N = read_ints()
    S = input().strip()
    opening = closing = 0
    left_add = 0
    for c in S:
        if c == '(':
            opening += 1
        else:
            closing += 1
        if closing > opening:
            left_add = max(left_add, closing-opening)
    opening = closing = 0
    right_add = 0
    for c in S[::-1]:
        if c == '(':
            opening += 1
        else:
            closing += 1
        if opening > closing:
            right_add = max(right_add, opening-closing)

    return '('*left_add+S+')'*right_add


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

Solution (Python):
N=int(input())
S=input()
R=[0 for i in range(N)]
L=[0 for i in range(N)]
LL=0
RR=0
for i in range(N):
  if S[i]=='(':
    LL+=1
  else:
    RR+=1
  L[i]=LL
  R[i]=RR
s=0
for i in range(N):
  s=max(s,R[i]-L[i])
t=s+L[N-1]-R[N-1]
print('('*s+S+')'*t)

Solution (Python):
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

N=intput()
S=input()
tmp=0
ans=deque()
for i in range(N):
    c=S[i]
    tmp = tmp+1 if c=='(' else tmp-1
    if tmp<0:
        ans.appendleft('(')
        tmp=0
    ans.append(c)
for _ in range(tmp):
    ans.append(')')
ans=list(ans)
lprint(ans,'')

Solution (Python):
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]


def main():
    n = i_input()
    s = input()

    l = 0
    r = 0

    for i in s:
        if i == ")" and r > 0:
            r -= 1
        elif i == ")":
            l += 1
        if i == "(":
            r += 1
    print("("*l + s + ")"*r)




if __name__=="__main__":
    main()

Solution (Python):
from collections import deque

N = int(input())
closings = list(input())
r_cnt = l_cnt = 0
for closing in closings:
  if closing == ')':
    if l_cnt > 0:
      l_cnt -= 1
    else:
      r_cnt += 1
  else:
    l_cnt += 1
answer = ['(' for _ in range(r_cnt)] + closings + [')' for _ in range(l_cnt)] 
print(''.join(answer))

Solution (Python):
def main():
    
    import sys
    input = lambda:sys.stdin.readline().strip()
    N = int(input())
    S = input()
    
    
    right=0
    left=0

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

if __name__=='__main__':
    main()

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

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

        if opens < 0:
            l += 1
            opens = 0

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

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

Solution (Python):
import sys

from collections import defaultdict


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    S = input()
    stack = []
    for s in S:
        if not stack:
            stack.append(s)
        elif s == "(":
            stack.append(s)
        elif s == ")":
            if stack[-1] == "(":
                stack.pop()
            else:
                stack.append(s)
    cnt = defaultdict(int)
    for s in stack:
        cnt[s] += 1
    left = cnt[")"]
    right = cnt["("]
    ans = ("(" * left) + S + (")" * right)
    print(ans)

    return


if __name__ == "__main__":
    main()

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

ans = S
count = 0

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

count = 0

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

    if(count>0):
        ans = ans + ")"
        count -= 1

print(ans)

Solution (Python):
with open(0) as f:
    N, S = f.read().split()
N = int(N)
S += '_'
left = 0
right = 0
cnt = 0
for i in range(N):
    cnt += {'(':1, ')':-1}[S[i]]
    if S[i] == ')' and S[i+1] != ')':
        if cnt < 0:
            left += -cnt
            cnt = 0
    if i == N-1 and cnt > 0:
        right += cnt
ans = '(' * left + S[:N] + ')' * right
print(ans)

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

keep = 0
ans = ''
for i in range(N):
    if s[i] == '(':
        ans += '('
        keep += 1
    else:
        if keep > 0:
            ans += ')'
            keep -= 1
        else:
            ans = ('(' + ans + ')')
print(ans + ')' * keep)

Solution (Python):
def main():
    n = int(input())
    s = input()
    l, r, c = 0, 0, 0
    for a in s:
        if a == '(':
            c += 1
        elif c:
            c -= 1
        else:
            l += 1
    r = c
    print("("*l + s + ")"*r)


if __name__ == "__main__":
    main()

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

Solution (Python):
def main():
    n = int(input())
    s = input()
    l, r, c = 0, 0, 0
    for a in s:
        if a == '(':
            c += 1
        else:
            if c:
                c -= 1
            else:
                l += 1
    r = c
    print("("*l + s + ")"*r)


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
s = input()
def f(s):
    d = 0
    for i in range(len(s)):
        if s[i] == "(":
            d += 1
        else:
            d -= 1
        if d < 0:
            return "("+s
    if d > 0:
        return s+")"
    else:
        print(s)
        exit(0)
while True:
    s = f(s)

Solution (Python):
n=int(input())
s=input()
l=[]
for i in s:
  if i==')':
    if len(l)>0:
      if l[-1]=='(':
        l.pop()
      else:
        l.append(i)
    else:
      l.append(i)
  else:
    l.append(i)
print(l.count(')')*'(' + s +l.count('(')*')')

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

cnt_rgt = 0
cnt = 0
for i in range(len(S)):
    if S[i]=="(":
       cnt += 1
    if S[i]==")":
        cnt -= 1
        if cnt<0:
            cnt = 0
            cnt_rgt += 1

rgt = "("*cnt_rgt
lft = ")"*cnt

print(rgt+S+lft)

Solution (Python):
N=int(input())
S=input()
d = [0]*(N+1) 
              
for i in range(1, N+1):
    d[i] = S[:i].count("(") - S[:i].count(")")
x = min(d)

if x == 0 and d[N] == 0:
    print(S)
    exit()

ans = "("*abs(x) + S + ")"*(d[N]+abs(x))
print(ans)

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

for i in range(50):
  x=x.replace('()','')

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

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

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

print(s)

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

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

Solution (Python):
n = int(input())
s = input()
countr, countl = 0, 0

for i in range(n-1, -1, -1):
    if s[i] == ')': countr += 1
    elif countr > 0: countr -= 1
s = '('*countr+s
n = len(s)

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

print(s)

Solution (Python):
def main2():
    input()
    s = input()
    pair = [-1] * 2
    ans = s
    idx = 0
    for idx in range(0, len(s)):
        for i in range(idx, len(s)):
            if s[i] == '(':
                pair[0] = i if pair[0] == -1 else pair[0]
            elif s[i] == ')':
                pair[1] = i
                break
        if pair[0] != -1 and pair[1] != -1:
            s = s[:pair[0]] + ' ' + s[pair[0]+1:pair[1]] + ' ' + s[pair[1]+1:]
        elif pair[0] != -1 and pair[1] == -1:
            s = s[:pair[0]] + ' ' + s[pair[0]+1:]
            ans = ans + ')'
        elif pair[0] == -1 and pair[1] != -1:
            s = s[:pair[1]] + ' ' + s[pair[1]+1:]
            ans = '(' + ans
        pair = [-1] * 2
    print(ans)


if __name__ == '__main__':
    main2()

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

m = 0
now = 0
for i in s:
    if i == ')':
        now += 1
        if m < now:
            m = now
    else:
        now -= 1

print('('*m + s + ')'*(m + 2*s.count('(') - len(s)))

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

cntr = 0
for i in range(n-1, -1, -1):
    if s[i] == ')':
        cntr += 1
    elif cntr > 0:
        cntr -= 1
s = '(' * cntr + s
n = len(s)

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

print(s)

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

Solution (Python):
n=int(input())
S=input()
x=y=0
for i,s in enumerate(S):
  y=y-1 if s=='(' else y+1
  x=max(x,y)
print('('*x+S+')'*(x-y))

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

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

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

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

for n in range(N):
  T = T.replace("()","")

L = T.count("(")
R = T.count(")")
S = R*"("+S+L*")"
print(S)

Solution (Python):

import sys

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


sys.setrecursionlimit(10**7)









INF = 1 << 50
def run():
    N = int(input())
    S = input()
    position = 0
    l = 0
    r = 0
    for s in S:
        if s == '(':
            position += 1
        else:
            position -= 1
        if position < 0:
            l += abs(position)
            position = 0
    r += position

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

if __name__ == "__main__":
    run()

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

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

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

Solution (Python):
icase=0
if icase==0:
    n=int(input())
    s=input()
elif icase==1:
    n=3
    s="())"
elif icase==2:
    n=6
    s=")))())"
elif icase==3:
    n=8
    s="))))(((("

l=[]
r=[]
sim=s[0]
if sim=="(":
    lidx=0
    l.append(1)
    ridx=-1
elif sim==")":
    lidx=0
    l.append(0)
    ridx=0
    r.append(1)

for i in range(1,len(s)):
    if s[i]=="(" and s[i-1]=="(":
        l[lidx]+=1
    elif s[i]=="(" and s[i-1]==")":
        lidx+=1
        l.append(1)
    elif s[i]==")" and s[i-1]==")":
        r[ridx]+=1
    elif s[i]==")" and s[i-1]=="(":
        ridx+=1
        r.append(1)

ll=sum(l)
rr=sum(r)
ds=ll-rr

if len(l)>len(r):
    r.append(0)
xmin=0
x=0
for i in range(len(l)):
    x=x+l[i]-r[i]
    xmin=min(x,xmin)
    
strs="("*(-xmin) + s + ")"*(ds-xmin)
print(strs)

Solution (Python):

icase=0
if icase==0:
    n=int(input())
    s=input()
elif icase==1:
    n=3
    s="())"
elif icase==2:
    n=6
    s=")))())"
elif icase==3:
    n=8
    s="))))(((("

l=[]
r=[]
sim=s[0]
if sim=="(":
    lidx=0
    l.append(1)
    ridx=-1
elif sim==")":
    lidx=0
    l.append(0)
    ridx=0
    r.append(1)

for i in range(1,len(s)):
    if s[i]=="(" and s[i-1]=="(":
        l[lidx]+=1
    elif s[i]=="(" and s[i-1]==")":
        lidx+=1
        l.append(1)
    elif s[i]==")" and s[i-1]==")":
        r[ridx]+=1
    elif s[i]==")" and s[i-1]=="(":
        ridx+=1
        r.append(1)

ll=sum(l)
rr=sum(r)
ds=ll-rr

if len(l)>len(r):
    r.append(0)
elif len(l)<len(r):
    l.append(0)
xmin=100
x=0
for i in range(len(l)):
    x=x+l[i]-r[i]
    xmin=min(x,xmin)
if xmin>0:
    xmin=0
    
strs="("*(-xmin) + s + ")"*(ds-xmin)
print(strs)

Solution (Python):
N = int(input())
S = input().rstrip()
cnt1, cnt2 = 0, 0
for s in S:
    if s == "(":
        cnt1 += 1
    if s == ")" and cnt1 >= 1:
        cnt1 -= 1
for s in reversed(S):
    if s == ")":
        cnt2 += 1
    if s == "(" and cnt2 >= 1:
        cnt2 -= 1
print("("*cnt2 + S + ")"*cnt1)

Solution (Python):
from itertools import accumulate
N = int(input())
S = input()

m = -min(min(accumulate(1 if c == '(' else -1 for c in S)),0)
s = sum(1 if c == '(' else -1 for c in S)

print('('*m+S+')'*(s+m))

Solution (Python):
n = int(input())
N = input()
L = 0
R = 0
num = 0
for c in N:
    if c == '(':
        num += 1
    else:
        if num:
            num -= 1
        else:
            L += 1
R = num

print('(' * L + N + ')' * R)

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 = "".join(["("*l , S, ")"*r])
print(ans)

Solution (Python):
N=int(input())
S=input()
i=0
hidari=str()
migi=str()
a=0
while i<N:
  if S[i]==")":
    hidari+="("
    i+=1
  else:
    break
while i<N:
  if S[i]=="(":
    a+=1
  else:
    a-=1
  i+=1
if a<0:
  hidari+=abs(a)*"("
elif a>0:
  migi+=a*")"
s=hidari+S+migi


i=0
hidari=str()
migi=str()
a=0
while i<N:
  if S[i]==")":
    hidari+="("
    i+=1
  else:
    break
while i<N:
  if S[i]=="(":
    if a<0:
      a=0
    a+=1
    mina=0
  else:
    a-=1
    if a<0:
      if mina>a:
        hidari+="("
  i+=1
if a>0:
  migi+=a*")"
t=hidari+S+migi
if len(s)==len(t):
  print(s)
elif len(s)>len(t):
  print(s)
else:
  print(t)

Solution (Python):
from collections import deque

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

l, que = 0, deque([])
for i in s:
    que.append(i)
    if i == '(':
        l += 1
    elif i == ')':
        if l == 0:
            que.appendleft('(')
            l += 1
        l -= 1
print(*que, ')' * l, sep='')

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

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

ans = "".join(S)
if b > 0:
  ans = "("*b + ans
if a > 0:
  ans = ans + ")"*a
print(ans)

Solution (Python):
import sys, math, re
from functools import lru_cache
from collections import defaultdict
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

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

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N = ii()
    S = input()
    l = [0]
    for i in range(N):
        if S[i] == '(':
            l.append(l[-1]+1)
        else:
            l.append(l[-1]-1)

    m = min(l)

    if m < 0:
        l = list(map(lambda x: x-m, l))

    print('('*l[0] + S + ')'*l[-1])

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

l, que = 0, deque([])
for i in s:
    que.append(i)
    if i == '(':
        l += 1
    if i == ')':
        if l == 0:
            que.appendleft('(')
        else:
            l -= 1
print(*que, ')' * l, sep='')

Solution (Python):
N = int(input())
S = input()
now = 0
right = 0
left = 0
add_left = 0
while now < N:
    if S[now] == '(':
        left += 1
    else:
        if left:
            left -= 1
        else:
            add_left += 1
    now += 1
for _ in range(add_left):
    print('(', end='')
print(S, end='')
for _ in range(left):
    print(')', end='')

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

oS = S
S = list(S)

cnt = 0
while True:
    p_cnt = cnt
    for i in range(len(S) - 1):
        if S[i] == "(" and S[i + 1] == ")":
            S.pop(i + 1)
            S.pop(i)
            cnt += 1
            break

    if cnt == p_cnt:
        break

cnt_open = 0
cnt_close = 0

for s in S:
    if s == "(":
        cnt_open += 1
    else:
        cnt_close += 1

ans = ("(" * cnt_close) + oS + (")" * cnt_open)
print(ans)

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

l = 0
r = 0
p = []
for i in range(n):
  if s[i] == "(": p.append("(")
  else:
    if p == []: l += 1
    else: p.pop()
r = p.count("(")
print("("*l + s + ")"*r)

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


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

    count = 0
    for i in range(N)[::-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 = list(input())
stack = []
for i in range(n):
    if s[i] == "(":
        stack.append("(")
    elif len(stack) == 0 or stack[-1] == ")":
        stack.append(")")
    else:
        stack.pop()
stack = sorted(stack, reverse=True)
idx = 0
while idx < len(stack):
    if stack[idx] == "(":
        break
    else:
        print("(", end="")
    idx+=1
for ch in s:
    print(ch, end="")
for i in range(idx, len(stack)):
    print(")", end="")

Solution (Python):
n, s = int(raw_input()), raw_input()
h = {'(':+1 , ')':-1}
m = 0
bal = 0
for i in range(len(s)):
	bal += h[s[i]]
	m = min(bal,m)

print '(' *abs(m) + s + ')' * (bal + abs(m))

Solution (Python):
n, s = int(raw_input()), raw_input()
h = {'(':+1 , ')':-1}
m = 0
bal = 0
for i in range(len(s)):
	bal += h[s[i]]
	m = min(bal,m)

print '(' *abs(m) + s + ')' * max(0,bal + abs(m))

Solution (Python):

input()
s = input()
c = 0
for i in s:
    if i == "(":
        c += 1
    else:
        if c > 0:
            c -= 1
d = 0
for i in s[::-1]:
    if i ==")":
        d += 1
    else:
        if d > 0:
            d -= 1
print("("*d+s+")"*c)

Solution (Python):
import sys

input = sys.stdin.readline


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

    L = 0
    R = 0
    for s in S:
        if s == "(":
            R += 1
        else:
            if R > 0:
                R -= 1
            else:
                L += 1

    ans = "".join(["(" * L, S, ")" * R])
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def Level(S):
    A=[0]
    for i in range(len(S)):
        if S[i]=="(":
            A.append(A[-1]+1)
        else:
            A.append(A[-1]-1)
    return A

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

A=Level(S)
X=-min(A)
T="("*X+S

B=Level(T)
Y=B[-1]
U=T+")"*Y

print(U)