Problem:
 Score : 400 points    Problem Statement You are given a string S of length N consisting of ( and ) . Your task is to insert some number of ( and ) into S to obtain a correct bracket sequence . Here, a correct bracket sequence is defined as follows:   () is a correct bracket sequence.  If X is a correct bracket sequence, the concatenation of ( , X and ) in this order is also a correct bracket sequence.  If X and Y are correct bracket sequences, the concatenation of X and Y in this order is also a correct bracket sequence.  Every correct bracket sequence can be derived from the rules above.   Find the shortest correct bracket sequence that can be obtained. If there is more than one such sequence, find the lexicographically smallest one.      Constraints  The length of S is N .  1 ≤ N ≤ 100  S consists of ( and ) .         Input Input is given from Standard Input in the following format:  N  S       Output Print the lexicographically smallest string among the shortest correct bracket sequences that can be obtained by inserting some number of ( and ) into S .        Sample Input 1 3
())      Sample Output 1 (())       Sample Input 2 6
)))())      Sample Output 2 (((()))())       Sample Input 3 8
))))((((      Sample Output 3 (((())))(((())))

Solution (Python):
def main():
    from sys import setrecursionlimit, stdin
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**9+10

    N=II()
    S=input()
    p = 0
    num_right_p = 0
    ans = ''
    r = 0
    for s in S:
        if s == '(':
            p += 1
        else:
            if p > 0:
                p -= 1
            else:
                r += 1

    
        ans = '(' * r + S + ')' * p
    print(ans)
            
    

    
main()

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

from collections import deque

n = ni()
s = ns()

q = deque()
for i in range(n):
    p = q.pop() if len(q) else '$'
    if not (p == '(' and s[i] == ')'):
        if p != '$':
            q.append(p)
        q.append(s[i])

ans = deque(s)
for c in q:
    if c == ')':
        ans.appendleft('(')
    else:
        ans.append(')')

print(*ans, sep="")

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

stock = 0
L_cnt = 0
for s in S:
    if s == "(":
        stock += 1
    if s == ")":
        if stock == 0:
            L_cnt += 1
        else:
            stock -= 1

print("(" * L_cnt + S + ")" * stock)

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

nopen = 0
sl = ''
sr = ''

for c in s:
    if c == '(':
        nopen += 1
    else:
        if nopen == 0:
            sl += '('
        else:
            nopen -= 1

nopen = sum([1 if c == '(' else -1 for c in sl + s])
sr = ')' * nopen


print(sl + s + sr)

Solution (Python):


import sys






























def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    def preprocess(seq, n):
        stripped = False
        for i in range(n-1):
            if seq[i] == '(' and seq[i+1] == ')':
                new_seq = seq[:i] + seq[i+2:]
                stripped = True
                break
        if stripped:
            return preprocess(new_seq, n-2)
        else:
            return seq
        

    n = ii()
    initial = input()
    L = list(initial)

    stripped = preprocess(L, n)
    
    left_p = stripped.count(')')
    right_p = stripped.count('(')

    print('(' * left_p + initial + ')' * right_p)

    




if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
S = list(input())
c = 0
l = []
for i in S:
    if i == "(":
        c += 1
    else:
        c -= 1
    l.append(c)

m = min(l)
if m < 0:
    for i in range(N):
        l[i] += (-m)

    M = l[-1]
    ans = ["("] *(-m) + S + [")"] *M
    
else:
    M = l[-1]
    ans = S + [")"] *M

output = "".join(ans)
print(output)

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

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

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

res = ""
for i in range(left):
    res += '('
res += s
for i in range(right):
    res += ')'
print(res)

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

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

ans = ""
for i in range(0, -minv):
    ans += "("
ans += s
for i in range(0, score-minv):
    ans += ")"
print(ans)

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

x=0
y=0

for i in S:
    if i=="(":
        x+=1
    else:
        if x<=0:
            y+=1
        else:
            x-=1
print("("*y+S+")"*x)

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

a = 0
b = 0

for i in S:
    if i == "(":
        a += 1
    else:
        if a <= 0:
            b += 1
        else:
            a -= 1

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

Solution (Python):
import sys
from collections import Counter
from collections import deque
import math
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))


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


i=0
c=0
while i<len(s):
    if s[i]=="(" and c<0:
        s="("*(-c)+s
        i-=c
        c=0
    elif s[i]=="(":
        c+=1
        i+=1
    else:
        c-=1
        i+=1

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

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

for i in range(1+n//2):
    ss = ss.replace("()","")

sta = ss.count("(")
end = ss.count(")")

print("("*end + s + ")"*sta)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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

    stack = deque([])
    right = 0
    for i in range(N):
        if S[i] == "(":
            stack.append(S[i])
        else:
            if stack:
                stack.pop()
            else:
                right += 1

    ans = "(" * right + S + ")" * len(stack)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

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

s = deque(S)

ans = []
r, l, cnt = 0, 0, 0

while s:
    q = s.popleft()
    if q == ')':
        cnt -= 1
        if cnt < 0:
            l += 1
            cnt += 1
    else:
        cnt += 1
        
if cnt > 0: r += cnt

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

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

for i in range(N+1):
    partial = S[:i]
    d.append(partial.count('(') - partial.count(')'))

a = -min(d)
b = d[-1]

print('(' * a + "".join(S) + ')' * (b + a))

Solution (Python):
l = int(input())
m = input()

l = 0
r = 0
b = 0
for i in m:
    if i == ")":
        l += 1
    else:
        r += 1
    m = "(" * max(l-r,0) + m
    r += max(l-r,0)
m += ")" * max(r-l,0)
print(m)

Solution (Python):




import math
import sys
import bisect
import heapq  
from collections import deque

inf = 10 ** 15
mod = 10 ** 9 + 7

n = int(input())
s = input()
stack = []
ans = deque(list(s))
countl = 0
countr = 0
for c in s:
    if c == '(':
        stack.append('(')
    if c == ')':
        if stack:
            stack.pop()
        else:
            countl+=1
countr = len(stack)
for i in range(countl):
    ans.appendleft('(')
for i in range(countr):
    ans.append(')')
print(''.join(ans))

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

b = 0
e = 0
for s in S:
    if s == ')':
        e += 1
    else:
        b += 1
    S = '(' * max(e-b, 0) + S
    b += max(e-b, 0)
S += ')' * max(b-e, 0)
print(S)

Solution (Python):
import sys

def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))

def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]

def to_bin(x: int) -> str: return format(x, 'b') 
def to_oct(x: int) -> str: return format(x, 'o') 
def to_hex(x: int) -> str: return format(x, 'x') 
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i):
            is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]

from itertools import accumulate as acc, combinations as combi, product, combinations_with_replacement as combi_dup
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left


def main():
    n = II()
    s = IS()
    dq = deque()
    l_cnt = r_cnt = 0
    for si in s:
        
        if si == '(':
            l_cnt += 1
            dq.append(si)
        elif si == ')':
            if l_cnt == 0:
                dq.appendleft('(')
                dq.append(si)
            elif l_cnt > 0:
                dq.append(si)
                l_cnt -= 1
    for _ in range(l_cnt):
        dq.append(')')

    print(''.join(dq))



if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():

    N = int(input())
    S = str(input())
    stack_rem = 0

    need_left = 0

    for i in range(N):
        if S[i] == '(':
            stack_rem += 1
        elif stack_rem > 0:
            stack_rem -= 1
        else:
            need_left += 1
    need_right = stack_rem
    print('('*need_left+S+')'*need_right)

resolve()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():

    N = int(input())
    S = str(input())
    pointer = 0
    need_left = 0

    for i in range(N):
        if S[i] == '(':
            pointer += 1
        else:
            if pointer == 0:
                need_left += 1
            else:
                pointer -= 1

    need_right = pointer
    print('('*need_left+S+')'*need_right)

resolve()

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    S = input().rstrip('\n')

    balance = 0
    balance_min = 0
    for s in S:
        if s == "(":
            balance += 1
        else:
            balance -= 1
        balance_min = min(balance_min, balance)
    ans = S
    if balance_min < 0:
        ans = "(" * (balance_min * -1) + S
        balance -= balance_min
    if balance > 0:
        ans += ")" * balance
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():

    N = int(input())
    S = str(input())
    left_over = 0
    right_over = 0

    for i in range(N):
        if S[i] == '(':
            left_over += 1
        else:
            left_over -= 1
            if left_over < 0:
                right_over = max(right_over, -left_over)

    SS = '('*right_over+S

    left_over = 0
    for i in range(len(SS)):
        if SS[i] == '(':
            left_over += 1
        else:
            left_over -= 1

    print(SS+')'*left_over)


resolve()

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

stock_left = 0
num_new_l = 0
for i in range(n):
    if s[i] == '(':
        stock_left += 1
    else:
        if stock_left > 0:
            stock_left -= 1
        else:
            num_new_l += 1

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

new_l = '(' * num_new_l
new_r = ')' * num_new_r
print(new_l + s + new_r)

Solution (Python):

import sys

def f(S):
    '''
    >>> f('(')
    '('
    >>> f(')(')
    ')('
    >>> f('()')
    ''
    >>> f('(())(')
    '('
    >>> f('())')
    ')'
     '''
    stack = []
    for s in S:
        if s == ')':
            if stack and stack[-1] == '(':
                stack.pop()
            else:
                stack.append(')')
        else:
            stack.append(s)
    return ''.join(stack)


def solve(N: int, S: str):
    s = f(S)
    return '(' * s.count(')') + S + ')' * s.count('(')



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    S = next(tokens)  
    print(solve(N, S))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    test()
    main()

Solution (Python):


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

left = [] 

for i, s in enumerate(S):
    if s == "(":
        left.append("(")
    else:
        if len(left) > 0:
            left.pop()
        else:
            S = "(" + S

for _ in range(len(left)):
    S += ")"

print(S)

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

sl = 0
sr = 0
slmax = 0
srmax = 0
for i in range(N):
  if(S[i] == '('):
    sl -= 1
  else:
    sl += 1
  slmax = max(slmax, sl)
for i in range(N):
  if(S[N-i-1] == '('):
    sr += 1
  else:
    sr -= 1
  srmax = max(srmax, sr)
for i in range(slmax):
  S = '(' + S
for i in range(srmax):
  S = S + ')'
print(S)

Solution (Python):
N = int(input())
S = input()
LR = [0,0]
l = "("
r = ")"

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

S = l * LR[0] + S + r * LR[1]

print(S)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)

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

op, cl = 0 ,0


for c in s:
    if c == '(':
        op += 1
    else:
        if op > 0:
            op -= 1
        else:
            cl += 1

print(('(' * cl) + s + (')' * op))

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

c = [0,0]
for s in S:
    if s == '(':
        c[0] += 1
    else:
        if c[0] > 0:
            c[0] -= 1
        else:
            c[1] += 1

pre = ['('] * c[1]
rear = [')'] * c[0]
ans = pre+S+rear
print(''.join(ans))

Solution (Python):
n=int(input())
s=input()
d=[0]*n
lcount=0
rcount=0
for i in range(len(s)):
  if s[i]=="(":
    lcount+=1
  else:
    if lcount>=1:
      lcount-=1
    else:
      rcount+=1

print("("*rcount+s+")"*lcount)

Solution (Python):
from collections import deque
n=int(input())
s=input()
ans=deque(s)
cnt=0
for i in range(n):
  if (cnt==0)and(s[i]==')'):
    ans.appendleft('(')
  elif (cnt!=0)and(s[i]==')'):
    cnt-=1
    pass
  elif s[i]=='(':
    cnt+=1
if cnt>0:
  ans.append(')'*cnt)
print(''.join(ans))

Solution (Python):
N = int(input())
S = input()
SL = [0]
for i in range(N):
    if S[i] == '(':
        SL.append(SL[i] + 1)
    else:
        SL.append(SL[i] - 1)

mi = min(SL)
la = SL[-1]
if mi < 0:
    S = '(' * ((-1)*mi) + S
    la -= mi
if la >= 0:
    S += ')' * la
else:
    p = (-1)*la
    S = '(' * p + S

print(S)

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

left=0
cnt1=0
cnt2=0

for i in range(N):
    if S[i]=="(":
        cnt1+=1
    elif S[i]==")":
        cnt2+=1
        if i<N-2 and S[i+1]=="(":
            if cnt2>=cnt1+left:
                left=cnt2-cnt1

res=S.count("(")+left-S.count(")")
if res>=0:
    print("("*left+S+")"*res)
else:
    print("("*(left+abs(res))+S)

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

L = 0
R = 0
cnt = 0
d = []
for s in S:
    if s == "(":
       cnt += 1
    else:
        cnt -= 1
        if cnt < 0:
            cnt = 0
            L += 1

R += cnt

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

Solution (Python):

def hoge(S):
    cum = 0
    mi = 0
    for s in S:
        cum += 1 if s == '(' else -1
        mi = min(mi, cum)
    return (-mi, cum - mi)

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

l, r = hoge(S)
print('(' * l + S + ')' * r)

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

if cnt>0:
    while cnt>0:
        ans+=")"
        cnt-=1

print(ans)

Solution (Python):
N=int(input())
S=input()
stack= []
ans=""
L=0
R=0

for i in range(N):
  if S[i]=="(":
    stack.append(S[i])
  else:
    if len(stack)>0:
      stack.pop()
    else:
      L += 1

R=len(stack)
ans = L * "(" + S + R * ")"

print(ans)

Solution (Python):
def solve():
    N = int(input())
    S = input()
    l,r = 0,0
    state = 'r'
    for i in range(N):
        if i == 0 and S[i] == ')': state = 'l'
        
        if i > 0  and S[i-1] == ')' and S[i] == '(':
            state = 'r' 
            
        if S[i] == '(':
            if state == 'l':
                if l > 0:
                    l -= 1
                else:
                    r += 1
            elif state == 'r':
                r += 1
        elif S[i] == ')':
            if state == 'r':
                if r > 0:
                    r -= 1
                else:
                    l += 1
            elif state == 'l':
                l += 1
                
        
            
    print('('*l+S+')'*r)
    
solve()

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

Solution (Python):
N = int(input())
S = input()
total,min_total = 0, 1
for s in S:
    total += 1 if s == '(' else -1
    if total < min_total:
        min_total = total    
print('('*-min_total+S+')'*(total-min_total) if min_total<0 else S+')'*total)

Solution (Python):
n = int(input())
s = input()
dist = 0
mlow = 0
for i in s:
    if i == ")":
        dist -= 1
        if dist < mlow:
            mlow = dist
    else:
        dist += 1

left = "("*(-mlow)
right = ")"*(dist-mlow)
print(left+s+right)

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

def main():
    N = int(readline())
    S = readline().rstrip()
    res = S[:]

    pls_left = 0
    pls_right = 0
    for s in S:
        if s == '(':
            pls_right += 1
        else:
            if pls_right == 0:
                pls_left += 1
            else:
                pls_right -= 1

    res = '(' * pls_left + S + ')' * pls_right

    print(res)

if __name__ == '__main__':
    main()

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

def main():
    N = int(readline())
    S = readline().rstrip()
    res = S[:]

    pls_left = 0
    pointer = 0
    for s in S:
        if s == '(':
            pointer += 1
        else:
            if pointer == 0:
                pls_left += 1
            else:
                pointer -= 1

    pls_right = pointer
    res = '(' * pls_left + S
    res += ')' * pls_right

    print(res)

if __name__ == '__main__':
    main()

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

result=""
cnt=0


for ss in s:
    
    if ss ==")":
        if cnt>0:
            result+=ss
            cnt-=1
        else:
            result="("+result+ss

    else:
        result+=ss
        cnt+=1

L=result.count("(")
R=result.count(")")

result+=")"*(L-R)

print(result)

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

Solution (Python):
N = int(input())
S = input()
l = 0
cnt = 0
for c in S:
    if c == "(":
        cnt += 1
    else:
        if cnt == 0:
            l += 1
        else:
            cnt -= 1
ans = "("*l + S + ")"*cnt
print(ans)

Solution (Python):
from itertools import accumulate
N = int(input())
S = input()
SS = [1 if S[i]=='(' else -1 for i in range(N)]
SSS = list(accumulate(SS))
m = max(0,-min(SSS))
M = SSS[-1]
print('('*m+S+')'*(M+m))

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

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

for i in range(ans):
    print('(',end="")
print(s,end="")
for i in range(count1):
    print(')',end="")

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

if __name__ == '__main__':
    main()

Solution (Python):

n = int(input())

s = input()

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

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

Solution (Python):
n = int(input())
x = list(input())
sta = 0
left = 0
for i in range(n):
    if x[i] == '(':
        sta += 1
    else:
        if sta == 0:
            left += 1
        else:
            sta -= 1
s = []
for i in range(left):
    s.append('(')
for i in range(n):
    s.append(x[i])
for i in range(sta):
    s.append(')')
print(''.join(s))

Solution (Python):
n = int(input())
t = input()
lef = 0
rig = 0
cl = 0
cr = 0

for i in range(n):
    if t[i] == ")":
        rig += 1
        if rig > lef+cl:
            cl += 1
    if t[i] == "(":
        lef += 1
lef = 0
rig = 0
for i in reversed(range(n)):
    if t[i] == "(":
        lef += 1
        if lef > rig+cr:
            cr += 1
    if t[i] == ")":
        rig += 1

for i in range(cl):
    print("(",end="")
print(t,end="")
for i in range(cr):
    print(")",end="")

Solution (Python):
input()
s = input()
d = 0
x = 0
for c in s:
    if c == "(":
        d += 1
    else:
        d -= 1
    x = min(d, x)
print("(" * -x + s + ")" * (d - x))

Solution (Python):




n = int(input())
s = list(input())
nestlv = 0
nestmax = 0
nestmin = 0
lcnt = 0
rcnt = 0

for i in range(n):
    if s[i] == '(':
        nestlv = nestlv + 1
        nestmax = max(nestmax, nestlv)
    elif s[i] == ')':
        nestlv = nestlv - 1
        nestmin = min(nestmin, nestlv)

ans = ''.join(s)
for i in range(nestmin*(-1)):
    ans = '(' + ans

nestlv = nestlv - nestmin
if nestlv > 0:
    for i in range(nestlv):
        ans = ans + ')'


print(ans)

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

cs=0
mincs=1000
enc={'(':1,')':-1}

for c in S:
    cs+=enc[c]
    mincs=min(mincs,cs)

while mincs<0:
    S='('+S
    mincs+=1
    cs+=1

while cs>0:
    S=S+')'
    cs-=1

print(S)

Solution (Python):
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



def warshall_floyd(d):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d



def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


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 lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)


def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True



def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret



n = int(input())
s = input()
cnt = 0
left = 0
for i in range(n):
    if s[i] == "(":
        cnt += 1
    elif cnt > 0:
        cnt -= 1
    else:
        left += 1
ans = "(" * left + s + ")" * cnt
print(ans)

Solution (Python):
def main():
  n=int(input())
  s=input()
  sl,sr=[0],[0]
  l,r=0,0
  for si in s:
    if si=='(':
      l+=1
    else:
      r+=1
    sr.append(r)
    sl.append(l)
  ans=n
  al,ar=0,0
  for i in range(n):
    if s[i]=='(':
      a=(sl[n]-sl[i+1])-(ar+sr[n]-sr[i+1])
      if a>=0:
        ar+=a+1
    else:
      a=sr[i]-(al+sl[i+1])
      if a>=0:
        al+=a+1
  print('('*al+s+')'*ar)
if __name__=='__main__':
  main()

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


S_orig=list(S)
while True:
  update=False
  
  remove_flg=[False]*len(S)
  for i in range(1,len(S)):
    if S[i-1]=='(' and S[i]==')':
      remove_flg[i-1]=remove_flg[i]=True
      update=True      
  if not update:
    break
      
  new_S=[]
  for i in range(len(S)):
    if not remove_flg[i]:
      new_S.append(S[i])      
  S=new_S
  
cnt_l=cnt_r=0
for i in range(len(S)):
  if S[i]=='(':
    break
  else:
    cnt_l+=1
for i in reversed(range(len(S))):
  if S[i]==')':
    break
  else:
    cnt_r+=1


answer_S=['(']*cnt_l+S_orig+[')']*cnt_r
print("".join(answer_S))

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

front_not_close = 0
end_not_close = 0

for s in list(S):
    if s == '(':
        front_not_close += 1
    else:
        if front_not_close > 0:
            front_not_close -= 1
        else:
            end_not_close += 1


for i in range(end_not_close):
    S = '(' + S

for i in range(front_not_close):
    S = S + ')'

print(S)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = int(input())
    S = input()
    stack = deque([])
    left = 0
    for s in S:
        if s == "(":
            stack.append(s)
        else:
            if len(stack) == 0:
                left += 1
            else:
                _ = stack.pop()

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


if __name__ == "__main__":
    main()

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

d = [0] * (N + 1)
for i in range(N):
    d[i + 1] = d[i] + int(S[i] == "(") - int(S[i] == ")")

a = d[-1]
b = min(d)

print("(" * -b + S + ")" * (a - b))

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

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

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

Solution (Python):
n = int(input())
s = input()
ss = s
l = 0
for c in ss:
    if c == "(":
        l += 1
    else:
        if l > 0:
            l -= 1
        else:
            s = "(" + s
for i in range(l):
    s = s + ")"
print(s)

Solution (Python):
n = int(input())
s = input()
l=0
r=0
for i in s:
    if i ==')' and l==0:
        r+=1
    elif i==')':
        l-=1
    elif i=='(':
        l+=1
s1 = '('*r
s2 = ')'*l
s=s1+s+s2
print(s)