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





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()
	
	A=[]
	if s[0]==")":
		A.append(0)
	s+="0"
	cnt=1
	for i in range(n):
		if s[i]==s[i+1]:
			cnt+=1
		else:
			A.append(cnt)
			cnt=1
	
	
	l=0
	r=0
	now=0
	for i in range(len(A)):
		
		if i%2:
			r+=2*min(A[i],now)
			l+=max(A[i]-now,0)
			now=max(now-A[i],0)
		else:
			now+=A[i]
	
	
	ans="("*l+s[:-1]+")"*(n-l-r)
	print(ans)
	
	
	
	
	
	

if __name__=="__main__":
	main()

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

left = ''
right = ''

skip_idx = []
for idx, s in enumerate(S):
    if idx in skip_idx:
        continue
    if s == ')':
        left += '('
    else:
        
        skip_flag = 0
        for n in range(idx+1, N):
            if n in skip_idx:
                continue
            if S[n] == ')':
                skip_idx.append(n)
                skip_flag = 1
                break
        if not skip_flag:
            right += ')'
    

print(left+S+right)

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

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

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

cd = []
q = []
for s in S:
    if q and q[-1]=="(":
        if s==")":
            q.pop()
        else:
            q.append(s)
    else:
        q.append(s)
sl = []
sr = []
for s in q:
    if s==")":
        sl.append("(")
    else:
        sr.append(")")
print("".join(sl)+S+"".join(sr))

Solution (Python):

from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

def main():
    N = int(input())
    T = input()
    S = []
    for s in T:
        if s == '(':
            S.append(1)
        else:
            S.append(-1)
    S = list(accumulate(S))
    
    minS = min(S)
    if minS < 0:
        for i in range(N):
            S[i] -= minS
    print('('*max(0,-minS) + T + ')'*S[-1])

if __name__ == "__main__":
    main()

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

cd = []
q = []
for s in S:
    if q and q[-1]=="(":
        if s==")":
            q.pop()
        else:
            q.append(s)
    else:
        q.append(s)
sl = []
sr = []
for s in q:
    if s==")":
        sl.append("(")
    else:
        sr.append(")")

print("".join(sl)+S+"".join(sr))

Solution (Python):
n = int(input())
data = [c for c in input()]
stack = []
ans = ''
for c in data:
    if c == '(':
        stack.append(c)
        ans += '('
    else:
        if len(stack) == 0 or stack.pop() != '(':
            ans = '(' + ans + c
        else:
            ans += ')'
ans += ')'*len(stack)

print(ans)

Solution (Python):
from collections import deque
n = int(input())
s = input()
A = deque([])
l = 0
r = 0
for i in range(n):
  if s[i]=='(':
    A.append(s[i])
    l += 1
  else:
    if l!=0:
      A.append(s[i])
      l -=1
    else:
      A.appendleft("(")
      A.append(s[i])

for j in range(l):
  A.append(")")
  
print("".join(A))

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

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

res = ""
st = []
for s in S:
    if s == "(":
        st.append("(")
        res += "("
    else:
        if st:
            st.pop()
            res += ")"
        else:
            res = "(" + res + ")"

print(res + ")" * len(st))

Solution (Python):
N = 6
S = ')))())'











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

def calculate(n, str):

    finalStr = ''
    while True:
        point = 0
        remainStr = ''
        for i in range(len(str)):
            if i > 0:
                if (str[i-1] == '(') and (str[i] == ')'):
                    point += 1
                    continue

            if i < (n - 1):
                if (str[i] == '(') and (str[i+1] == ')'):
                    point += 1
                    continue

            remainStr += str[i]

        str = remainStr
        n = len(str)
        if point == 0:
            finalStr = remainStr
            return finalStr
            break







res = calculate(N, S)

for i in range(len(res)):
    if res[i] == '(':
        S = S + ')'

    if res[i] == ')':
        S = '(' + S

print(S)

Solution (Python):
n = int(input())
s = input()
stack = []
cntLeft = 0
cntRight = 0
for ss in s:
    if ss == '(':
        stack.append('(')
    else:
        if len(stack) > 0:
            stack.pop()
        else:
            cntLeft += 1
cntRight = len(stack)
ans = ''
for i in range(cntLeft):
    ans += '('
ans += s
for i in range(cntRight):
    ans += ')'
print(ans)

Solution (Python):
import sys
from io import StringIO
import unittest
import os


sys.setrecursionlimit(999999999)



def resolve(test_def_name=""):
    n = int(input())
    s_s = list(input())

    

    for i in range(101):
        j = 0
        c = 0
        for cnt, s in enumerate(s_s):
            if s == "(":
                c += 1
            else:
                j += 1
            if c < j:
                s_s = ["("] + s_s
                break
            if cnt == len(s_s) - 1 and c > j:
                s_s = s_s + [")"]

    print("".join(s_s))
        
        
        
        
        
        
        

        


class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3
())"""
        output = """(())"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """6
)))())"""
        output = """(((()))())"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """8
))))(((("""
        output = """(((())))(((())))"""
        self.assertIO(test_input, output)

    
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

Solution (Python):
def main():
    n = int(input())
    S = input()
    left_shortage = 0
    now = 0
    for s in S:
        if s == "(":
            now += 1
        else:
            now -= 1
            left_shortage = min(now, left_shortage)

    right_shortage = 0
    now = 0
    for s in S[::-1]:
        if s == ")":
            now += 1
        else:
            now -= 1
            right_shortage = min(now, right_shortage)

    print("("*-left_shortage + S + ")"*-right_shortage)


if __name__ == "__main__":
    main()

Solution (Python):
n=int(input())
s=input()
a=[1 if i=='(' else -1 for i in s]
e=[0]
for i in range(n):
    e.append(e[i]+a[i])
s=-min(e)*'('+s
s+=(s.count('(')-s.count(')'))*')'
print(s)

Solution (Python):
n=int(input())
s=input()
cnt=0
for i in s:
    if i=="(": cnt+=1
    elif cnt>=1: cnt-=1
cnt2=0
for i in range(n-1,-1,-1):
    if s[i]==")": cnt2+=1
    elif cnt2>=1: cnt2-=1
print("("*cnt2+s+")"*cnt)

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

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



N = I()
S = list(input())

c = 0
now = 0
left = 0
right = 0
for i in range(N):
    if S[i] == '(':
        now -= 1
        left += 1
    else:
        now += 1
        right += 1
    if c < now:
        c = now

S = ['(']*c + S + [')']*(left+c-right)
print(''.join(S))

Solution (Python):
n = int(input())
s = input()
l_cnt = 0
r_cnt = 0
l_ans = 0
for i in s:
    if i == ')':
        if l_cnt:
            l_cnt -= 1
        else:
            l_ans += 1
    else:
        l_cnt += 1

print(l_ans*'(' + s + l_cnt*')')

Solution (Python):
n=int(input())
s=list(input())
ins=0
app=0
for i in range(n):
    if s[i]=='(':
        app += 1
    else:
        if app>0:
            app -= 1
        else:
            ins += 1
inL=['(']*ins
app=[')']*app
ans=inL+s+app
print(''.join(ans))

Solution (Python):
n = int(input())
s = str(input())
p = 0
q = 0
for i in range(n):
    if s[i] == ")":
        if q == 0:
            p += 1
        else:
            q -= 1
    else:
        q += 1
print("("*p+s+")"*q)

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

    l, r = 0, 0

    for i in s:
        if i == ")":
            if l:
                l -= 1
            else:
                r += 1
        else:
            l += 1

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


if __name__ == '__main__':
    main()

Solution (Python):

def resolve():
    N = int(input())
    S = list(input())
    nopen = 0
    addleft = 0
    addright = 0
    for s in S:
        if s == "(":
            nopen += 1
        else:
            if nopen == 0:
                addleft += 1
            else:
                nopen -= 1
    addright = nopen
    print("("*addleft+"".join(S)+")"*addright)


if __name__ == '__main__':
    resolve()

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
s = ins()
l = r = lv = rv = 0
for i in range(n):
    if s[i]=='(':
        l += 1
    elif l>0:
        l -= 1
    else:
        rv += 1
for i in range(n-1,-1,-1):
    if s[i]==')':
        r += 1
    elif r>0:
        r -= 1
    else:
        lv += 1
print('('*rv+s+')'*lv)

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

L = 0  
R = 0  
cnt = 0  

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

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

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

need_left = 0
pointer = 0

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

res = ""
for i in range(need_left):
    res += "("
res += s

for i in range(pointer):
    res += ")"

print(res)

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

ans = S
cnt = 0
now = ""
for s in S:
    now = s
    if s == "(":
        cnt += 1
    elif s == ")":
        cnt -= 1
    if cnt == -1:
        ans = "(" + ans
        cnt = 0
if cnt > 0:
    ans = ans + ")"*cnt

print(ans)

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

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

print(l_cnt * "(" + s + r_cnt * ")")

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]





n=ii()
s=ss()

cc = 0
res = s
for i in s:
    if i == "(":
        cc += 1
    elif i == ")":
        cc -= 1
        if cc < 0:
            res = "(" + res
            cc = 0

res += ")" * cc
print(res)

Solution (Python):
def main():
    n = int(input())
    S = input()
    a, b = 0, 0
    aa = 0
    m = 0
    for s in S:
        if aa > 0 and s == ')':
            m += 1
            aa -= 1
        if s == '(':
            a += 1
            aa += 1
        else:
            b += 1
    print(''.join(['(' * (b - m), S, ')' * (a - m)]))

if __name__ == '__main__':
    main()

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

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

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

Solution (Python):
from collections import deque
n = int(input())
s = list(input())
d = deque(s)
l, r = 0, 0
for i in range(n):
    if l == r and s[i] == ")":
        d.appendleft("(")
    elif s[i] == ")":
        r += 1
    else:
        l += 1
s = "".join(list(d))
print(s + ")" * max(0, l - r))

Solution (Python):



n = int(input())
s = list(input())
surplus_left, surplus_right = 0, 0
right_count, left_count = 0, 0
for i in range(n - 1, -1, -1):
    if s[i] == "(":
        if left_count > 0:
            left_count -= 1
        else:
            surplus_left += 1
    else:
        left_count += 1
for i in range(n):
    if s[i] == ")":
        if right_count > 0:
            right_count -= 1
        else:
            surplus_right += 1
    else:
        right_count += 1

print("(" * surplus_right + "".join(s) + ")" * surplus_left)

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

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

LR[1]=count
for i in range(2):
    for j in range(LR[i]):
        if i==0:
            S.insert(0,"(")
        else:
            S.append(")")

print("".join(S))

Solution (Python):
N = int(input())
S = input()
l = 0
r = 0
for i in range(N):
  if S[i] == ')':
    if r > 0:
      r-=1
    else:
      l+=1
  else:
    r+=1
for _ in range(l):
  print('(', end='')
print(S, end='')
for _ in range(r):
  print(')', end='')

Solution (Python):
def main():
  N = int(input())
  S = list(str(input()))
  num_1 = 0
  num_2 = 0
  for i in range(N):
    if S[i] == '(':
      num_1 += 1
    else:
      if num_1 > 0: num_1 -= 1
  for i in range(N-1, -1, -1):
    if S[i] == ')':
      num_2 += 1
    else:
      if num_2 > 0: num_2-=1
  for i in range(num_1):
    S.append(')')
  for i in range(num_2):
    S.insert(0, '(')
  print(''.join(S))

if __name__ == "__main__":
  main()

Solution (Python):
n = int(input())
S = input()
"""
)))((()())
-3  -1  
左に何個、右に何個
"""
l = 0
r = 0
prev = ")"

for s in S:
    if prev == ")" and s == ")":
        if r > 0:
            r -= 1
        else:
            l += 1
    elif prev == ")" and s == "(":
        r += 1
    elif prev == "(" and s == ")":
        r -= 1
    elif prev == "(" and s == "(":
        r += 1
    
    prev = s
ans = "("*l + S + ")"*r

print(ans)

Solution (Python):
n = int(input())
s = str(input())
ns = s
while '()' in ns:
    ns = ns.replace('()', '')
l = ns.count(')')
r = ns.count('(')
print('(' * l + s + ')' * r)

Solution (Python):

def resolve():
    N = int(input())
    S = input()
    left, right, cnt = 0,0,0

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

    if cnt>0:
        left = cnt

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

if __name__ == "__main__":
    resolve()

Solution (Python):
n=int(input())
s=input()
now=0
rec=0
for i in s:
    now+=(-1)**(i==")")
    rec=min(now,rec)
f,t="",""
if rec<0:
    f="("*-rec
    now-=rec
if now>0:
    t=")"*now
print(f+s+t)

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

left = 0
right = 0
left_ans = 0
right_ans = 0
for i in range(N):
    now = S[i]
    if now == "(":
        left += 1
    else:
        right += 1
        if left == 0:
            left_ans += 1
        else:
            left -= 1
            left = max(0, left)
            
S_mirror = ""
for i in range(N-1, -1, -1):
    if S[i] == "(":
        S_mirror += ")"
    else:
        S_mirror += "("

left = 0
right = 0
right_ans = 0
for i in range(N):
    now = S_mirror[i]
    if now == "(":
        left += 1
    else:
        right += 1
        if left == 0:
            right_ans += 1
        else:
            left -= 1
            left = max(0, left)        

ans = "("*left_ans + S + ")"*right_ans
print(ans)

Solution (Python):
from collections import deque

def main():
    N = int(input())
    S = list(input())
    Stmp = S.copy()
    Stmp = deque(Stmp)
    cnt = 0
    for s in S:
        cnt += (s=='(') - (s==')')
        if cnt < 0:
            Stmp.appendleft('(')
            cnt += 1
    for _ in range(cnt):
        Stmp.append(')')
    print(''.join(Stmp))

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    N = int(input())
    S = input()
    h_left, h_min, h_cur = 0, 0, 0
    for c in S:
        if c == '(':
            h_cur += 1
        else:
            h_cur -= 1
        h_min = min(h_min, h_cur)
    h_right = h_cur
    if h_min < 0:
        h_left -= h_min
        h_right -= h_min
    print('(' * h_left + S + ')' * h_right)


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
s=list(input())
cnt=0
right=0
left=0
for i in range(len(s)):
    if s[i] == '(':
        cnt+=1
    else:
        cnt-=1
    if cnt < 0:
        right+=1
        cnt=0
if cnt>0:
    left=cnt
for i in range(right):
    s.insert(0,'(')
for i in range(left):
    s.append(')')
print(''.join(s))

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

t=0

while t==0:
    b=0
    for i in range(len(s)):
        if s[i]=="(":
            b+=1
        else:
            b-=1
        if b<0:
            s="("+s+")"
            
            break
    if b==0:
        break
print(s)

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

l = "("
r = ")"

add_right, add_left = 0, 0

for c in s:
    if c == l:
        add_right += 1
    else:
        if add_right:
            add_right -= 1
        else:
            add_left += 1

print(l * add_left + s + r * add_right)

Solution (Python):
N=int(input())
n=input()
l=0;r=0
for i in n:
    if i=="(":
        r+=1
    else:
        if r:
            r-=1
        else:
            l+=1
print("("*l+n+")"*r)

Solution (Python):
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = int(input())
    s = input()[:-1].decode()
    c1 = 0
    c2 = 0
    for i in range(n):
        if s[i] == '(':
            c1 += 1
        elif s[i] == ')':
            c1 -= 1
        if c1 < 0:
            c1 = 0
            c2 += 1
    print('(' * c2, s, ')' * c1, sep='')


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

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

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

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

Solution (Python):
n = int(input())
string = input()
start_cnt = 0
end_cnt = 0
tmp = 0
for s in string:
    if s == ")":
        if tmp == 0:
            start_cnt += 1
        else:
            tmp -= 1
    else:
        tmp += 1
tmp = 0
for s in string[::-1]:
    if s == "(":
        if tmp == 0:
            end_cnt += 1
        else:
            tmp -= 1
    else:
        tmp += 1
for _ in range(start_cnt):
    print("(", end = "")
    
print(string, end = "")

for _ in range(end_cnt):
    print(")", end = "")
    
print()

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

ans = ''

lcount = 0
rcount = 0
now = 0
for i in range(N):
  si = S[i]
  if (lcount==0) and (si==')'):
    rcount += 1
    ans = '(' + ans + ')'
  elif si == ')':
    lcount -= 1
    ans = ans + ')'
  
  if (rcount>=1) and (si=='('):
    rcount = 0
    lcount = 1
    ans = ans + '('
  elif si == '(':
    ans = ans + '('
    lcount += 1
    

ans = ans + ')'*lcount
print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N = I()
S = S()

MIN = 0
SUM = 0

for s in S:
  if s == "(":
    SUM += 1
  else:
    SUM -= 1
    MIN = min(MIN,SUM)
print("("*abs(MIN)+S+")"*(SUM-MIN))

Solution (Python):
input()
s=t=input()
p,q=o="()"
exec('s=s.replace(o,"");'*50)
f=s.count
print(p*f(q)+t+q*f(p))

Solution (Python):
input()
t=s=input()
p,q=o="()"
while o in s:s=s.replace(o,"")
f=s.count
print(p*f(q)+t+q*f(p))

Solution (Python):
input()
t=s=input()
p,q=o="()"
while o in s:s=s.replace(o,"")
print(p*s.count(q)+t+q*s.count(p))

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

Solution (Python):
input()
s = input()
L = R = 0
for t in s:
    if t == "(":
        R += 1
    else:
        if R:
            R -= 1
        else:
            L += 1
print("("*L + s + ")"*R)

Solution (Python):
import sys


import math
import collections

import bisect
import itertools
import fractions

import copy
import heapq
import decimal

import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))





def main():
    n = ni()
    s = list(input())

    open_cnt = 0
    close_cnt = 0
    for si in s:
        if si == "(":
            open_cnt += 1
        else:
            if open_cnt == 0:
                close_cnt += 1
            else:
                open_cnt -= 1


    for i in range(close_cnt):
        s.insert(0, "(")

    for i in range(open_cnt):
        s.append(")")

    print(*s, sep="")


if __name__ == '__main__':
    main()

Solution (Python):






import sys
readline = sys.stdin.readline

N = int(readline())
S = readline().rstrip()

open = 0
a = 0
for i in range(len(S)):
  if S[i] == "(":
    open += 1
  else:
    if open == 0:
      a += 1
    else:
      open -= 1

print(a * "(" + S + ")" * open)

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

Solution (Python):
from sys import stdin
def main():
    
    readline=stdin.readline
    n=int(readline())
    s=readline().strip()

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

    print("("*need_left+s+")"*left_left)

if __name__=="__main__":
    main()

Solution (Python):
from sys import stdin
def main():
    
    readline=stdin.readline
    n=int(readline())
    s=readline().strip()

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

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

    print("("*need_left+s+")"*need_right)

if __name__=="__main__":
    main()

Solution (Python):
n = int(input())
s = input()
stack_len = 0
ans = ""
streak = 0
for i in s:
    if i == ")":
        if stack_len:
            stack_len -= 1
            ans += ")"
        else:
            ans = "(" + ans + ")"
    else:
        ans += "("
        stack_len += 1
ans += ")" * stack_len
print(ans)

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
s = ns().strip()
h = 0
minh = 0
for c in s:
    if c == "(":
        h += 1
    else:
        h -= 1
    minh = min(minh, h)
print("("*(-minh) + s + ")"*(h-minh))

Solution (Python):
n=int(input())
s=input()
stack=0
needleft=0
needright=0
for c in s:
    if c=='(':
        needright+=1
    else:
        if needright>0:
            needright-=1
        else:
            needleft+=1
s='('*needleft+s
s+=')'*needright
print(s)

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

while True:
    cum=[0]*(len(s)+1)
    for i,c in enumerate(s):
        cum[i+1]=cum[i]-1 if c==')' else cum[i]+1
    min_=min(cum)
    if min_<0:
        s='('*abs(min_)+s
        continue
    r=cum[-1]
    if r>0:
        s=s+')'*r
        continue
    print(s)
    exit()

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

Solution (Python):
def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    S = input()
    par = [0]
    cc = 0
    for i in S:
        if i == '(': cc += 1
        else: cc -= 1
        par.append(cc)

    mp = min(par)
    output = S
    if mp < 0: output = '(' * abs(mp) + output
    if abs(mp) + cc > 0: output = output + ')' * (abs(mp)+cc)
    print(output)

    return

if __name__ == '__main__':
    main()

Solution (Python):
import sys

N = int(sys.stdin.readline())
S = sys.stdin.readline().strip()

stack = []
for s_i in S:
    if not stack:
        stack.append(s_i)
    elif stack[-1] == "(" and  s_i == ")":
        stack.pop()
    else:
        stack.append(s_i)


left = 0
right = 0
for s_i in stack:
    if s_i == ")":
        right += 1
    else:
        left += 1

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

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

data = [0, 0]  
temp = -1
for i in range(n):
    temp += 1
    tar = s[temp]
    if (tar == '('):
        data[0] += 1

    else:
        if (data[0] > data[1]):
            data[0] -= 1
        else:
            s = '(' + s
            temp += 1


add = ')' * data[0]
s = s + add

print(s)