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

a=int(input())
b=input()
s1=s2=e1=e2=0
str1=str2=''

for i in range(len(b)):
    if( b[i] == '(' ):
        s1-=1
    elif( b[i] == ')' ):
        s1+=1
        if(s1>s2):
            s2=s1
            str1+='('

for i in range(len(b)-1,-1,-1):
    if( b[i] == '(' ):
        e1+=1
        if(e1>e2):
            e2=e1
            str2+=')'
    elif( b[i] == ')' ):
        e1-=1

print(str1 + b + str2)

Solution (Python):
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    s = list(str(input().rstrip('\n')))
    s = collections.deque(s)
    ds = collections.deque(s)
    while s:
        while True:
            ll = len(s)
            s = collections.deque(list("".join(s).replace("()", "")))
            if ll == len(s):
                break
        if len(s) != 0:
            if s[0] == "(":
                s.append(")")
                ds.append(")")
            else:
                s.appendleft("(")
                ds.appendleft("(")
        else:
            print("".join(ds))


if __name__ == '__main__':
    solve()

Solution (Python):



from collections import deque

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

ans = deque()
cnt = 0
for i in range(n):
    if s[i]==")":
        if cnt<=0:
            ans.appendleft("(")
            ans.append(")")
        else:
            ans.append(")")
            cnt -= 1
    else:
        ans.append("(")
        cnt += 1
for i in range(cnt):
    ans.append(")")

print(''.join(ans))

Solution (Python):
from collections import deque

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

open_ = 0  
close_ = 0  

ans = deque(s)
for c in s:
    if c == '(':
        open_ += 1
    else:
        close_ += 1
        if close_ > open_:
            ans.appendleft('(')
            close_ -= 1
for _ in range(close_ - open_):
    ans.appendleft('(')
for _ in range(open_ - close_):
    ans.append(')')
print(*ans, sep='')

Solution (Python):
n=int(input())
s=input()
data=[0]*n
for i in range(n):
    if s[i]=="(":
        data[i]=1
    else:
        data[i]=-1
for i in range(1,n):
    data[i]+=data[i-1]
k=data[-1]
l=min(data)
if l<0:
    l*=-1
    k+=l
    if k>=0:
        print("("*l+s+")"*k)
    else:
        print("("*(l-k)+s)
else:
    if k>=0:
        print(s+")"*k)
    else:
        print("("*(-k)+s)

Solution (Python):
n = int(input())
s = str(input())
r = [i for i in range(n) if s[i] == "("]
l = [i for i in range(n) if s[i] == ")"]
if r == []: print(n*"(" + s)
elif l == []: print(s + n*")")
elif min(r) > max(l):
    print(len(l)*"(" + s + len(r)*")")
else:
    cnt = 0
    for i in reversed(range(len(r))):
        if r[i] < max(l):
            cnt += 1
            l.pop(-1)
        if l == []: break
    print((len(l)) * "(" + s + (len(r) - cnt) * ")")

Solution (Python):
N=int(input())
S=list(input())
mS=[i for i in S]

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

print("".join(["("]*S.count(")")+mS+[")"]*S.count("(")))

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
S = list(input())[: -1]
x = 0
s = set()
for i in range(N):
  if S[i] == "(": x += 1
  else: continue
  for j in range(i, N):
    if j in s:
      continue
    if S[j] == ")":
      x -= 1
      s.add(j)
      break
y = 0
for i in range(N - 1, -1, -1):
  if S[i] == ")":
    if i in s: continue
    y += 1
  else: continue

if x > 0:
  S += [")"] * x
if y > 0:
  S = ["("] * y + S
print("".join(S))

Solution (Python):
N=int(input())
S=input()
L,R=0,0

for i in S:
    if i=='(':
        R+=1
    else:
        if R:  
            R-=1
        else:
            L+=1

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

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

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

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

if d[-1] < 0:
    d = [i for i in range(1, abs(d[-1]) + 1)] + [x - d[-1] for x in d]
m = min(d)
if m < 0:
    d = [i for i in range(1, abs(m) + 1)] + [x - m for x in d]
if d[-1] > 0:
    d = d + [i for i in reversed(range(d[-1]))]

ans = ''
for i, num in enumerate(d):
    if i == 0:
        ans += '('
    elif d[i] > d[i - 1]:
        ans += '('
    else:
        ans += ')'
print(ans)

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

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

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

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

for s in S:
    if stack:
        p = stack.pop()
        if p == "(" and s == ")":
            continue
        else:
            stack.append(p)
            stack.append(s)
    else:
        stack.append(s)

while stack:
    p = stack.pop()
    if p == "(":
        S = S + ")"
    else:
        S = "(" + S

print(S)

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

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

ans=0
v=[]
for i in range(n):
    ans+=s[i]
    if ans>0:
        v.append(-1)
        ans-=1
s=v+s
if ans<0:
    for i in range(abs(ans)):
        s.append(1)
for i in range(len(s)):
    if s[i]==-1:
        s[i]='('
    else:
        s[i]=')'
print(''.join(s))

Solution (Python):
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    s = list(str(input().rstrip('\n')))
    s1 = collections.deque(s)
    s2 = collections.deque(s)
    while True:
        ln = len(s1)
        while True:
            s1 = collections.deque(list("".join(s1).replace("()", "")))
            if len(s1) == ln:
                break
            else:
                ln = len(s1)
        if len(s1) == 0:
            break
        elif s1[0] == "(":
            s1.append(")")
            s2.append(")")
        else:
            s1.appendleft("(")
            s2.appendleft("(")
    print("".join(s2))


if __name__ == '__main__':
    solve()

Solution (Python):
n = int(input())
s = list(input())
global data
data = [[0 for i in range(n)] for j in range(2)]

for i in range(n):
    data[0][i] = s[i]
    
    data[1][i] = 0


def Lsearch(index):
    while index >= 0:
        if data[0][index] == '(' and data[1][index] == 0:
            data[1][index] = 1
            return False
        index -= 1
    return True

def Rsearch(index):
    if index >= len(data[0]):
        data[0].insert(len(data[0]), ')')
        data[1].insert(len(data[0]), 1)
        return
    elif data[0][index] == ')' and data[1][index] == 0:
        data[1][index] = 1
    else:
        Rsearch(index + 1)
i = 0
while i < len(data[0]):
    
    
    
    if data[0][i] == ')' and data[1][i] == 0:
        if Lsearch(i - 1):
            data[1][i] = 1
            data[0].insert(0, '(')
            data[1].insert(0, 1)
    
    elif data[0][i] == '(' and data[1][i] == 0:
        Rsearch(i + 1)
        data[1][i] = 1
    i += 1
print("".join(data[0]))

Solution (Python):

import collections

N = int(input().split()[0])
S = input()

ext_n_open, ext_n_close = 0, 0
sub_s = ""

for i, ch in enumerate(list(S)):
    if ch == "(":
        ext_n_open += 1
    else:
        if ext_n_open == 0:
            
            ext_n_close += 1
        else:
            
            ext_n_open -= 1

ans = "(" * ext_n_close + S + ")" * ext_n_open

print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
import sys,bisect,math,itertools,string,queue
from heapq import heappop, heappush
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))


n = inp()
s = input()
acc = [0] * n
L = ''
for i in range(n):
    if i == 0:
        if s[i] == '(':
            acc[i] = 1
        else:
            acc[i] = -1
    else:
        if s[i] == '(':
            acc[i] = acc[i-1] + 1
        else:
            acc[i] = acc[i-1] - 1
x = min(acc)
if x < 0:
    L += '(' * abs(x) + s + ')' * (acc[-1] - x)
else:
    L += s + ')' * acc[-1]
print(L)

Solution (Python):
n=int(input())
w=input()
l=0
r=0
m=0
for i in range(n):
  if w[i]=="(":
    l+=1
  else:
    r+=1
  m=max(m,r-l)
if m==0:
  if l>r:
    print(w+")"*(l-r))
  else:
    print("("*(r-l)+w)
else:
  if l>r:
    print("("*m+w+")"*(m+l-r))
  else:
    if l+m>r:
      print("("*m+w+")"*(-r+l+m))
    elif l+m==r:
      print("("*m+w)
    else:
      print("("*(r-l-m)+w)

Solution (Python):
n=int(input())
s=input()
stk=[]
cnt=0 
add=0
for i in s:
    if i=='(':
        stk.append(i)
    else:
        if not stk:
            cnt+=1 
        else:
            stk.pop()
add=len(stk)
print('('*cnt+s+')'*add)

Solution (Python):
n = int(input())
s = input()
l,r = 0,0
ans = ''

for i in s:
    ans += i
    if i=='(':
        l += 1
    else:
        r += 1
    if l-r<0:
        ans = '(' + ans
        l += 1

diff = l-r
ans += ')' * diff
print(ans)

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


l=0
r=0
ans = ""

for i in s:
  ans += i
  if i == "(":
    l += 1
  else:
    r += 1
  
  if l - r < 0:
    ans = "(" + ans
    l += 1
    
diff = l - r
ans += ")" * diff
print(ans)

Solution (Python):
from sys import stdin
N = int(stdin.readline().rstrip())
S = (stdin.readline().rstrip())
stack = []
l = 0
r = 0
for i in range(N):
    if S[i] == "(":
        stack.append(1)
    elif S[i] == ")":
        if not stack:
            l += 1
        else:
            stack.pop()

r = len(stack)
print(l*"(" + S + r*")")

Solution (Python):
from collections import deque

N = int(input())
S = list(input())
stack = deque()
ans = ""
for s in S:
  ans += s
  if s == "(":
    stack.append(s)
  else:
    if not stack:
      ans = "("+ans
    else:
      _ = stack.pop()
if stack:
  ans += ")"*len(stack)
print(ans)

Solution (Python):
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    s = str(input().rstrip('\n'))
    t = s
    while True:
        l_len = len(s)
        while True:
            s = s.replace("()", "")
            if len(s) == l_len:
                break
            else:
                l_len = len(s)
        if len(s) == 0:
            print(t)
            exit()
        else:
            if s[0] == ")":
                s = "".join((list("(") + list(s)))
                t = "".join((list("(") + list(t)))
            else:
                s = "".join((list(s)) + list(")"))
                t = "".join((list(t)) + list(")"))


if __name__ == '__main__':
    slove()

Solution (Python):
N = int(input())
S = input().strip()
A = [0 for _ in range(N+1)]
for i in range(N):
    if S[i]=="(":
        A[i+1] = A[i]+1
    else:
        A[i+1] = A[i]-1
amin = min(A)
a = A[-1]
if amin>=0:
    x = S+")"*a
else:
    x = "("*abs(amin)+S
    a += abs(amin)
    x = x+")"*a
print(x)

Solution (Python):
N=int(input())
S=input()
a,t=0,0
for i in S:
    if i==")":
        t+=1
        a=max(a,t)
    else:
        t-=1
b,t=0,0
for i in range(N-1,-1,-1):
    if S[i]=="(":
        t+=1
        b=max(b,t)
    else:
        t-=1
print("("*a,end="")
print(S,end="")
print(")"*b,end="")

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

lcount = 0
rcount = 0

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

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

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
from collections import deque

def main():
    n = int(input().strip())
    S = input().strip()
    s = deque(S)
    st = []
    for c in S:
        if c == ')':
            if len(st) == 0:
                s.appendleft('(')
            else:
                st.pop()
        else:
            st.append('(')
    s.append(')' * len(st))
    print(''.join(s))

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
S = input()
a = S.count('(')
b = S.count(')')
ans = ''

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

ans += S + ')' * cnt
print(ans)

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

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

result = "(" * rest_right_parenthesis + s + ")" * rest_left_parenthesis
print(result)

Solution (Python):
N = int(input())
S = input()
cnt = 0
revS = []
for s in reversed(S):
    revS.append(s)
for s in S:
    if s == "(":
        cnt += 1
    else:
        if cnt <= 0:
            print("(", end="")
        if cnt > 0:
            cnt -= 1
print(S,end="")
cnt = 0
for s in revS:
    if s == ")":
        cnt += 1
    else:
        if cnt <= 0:
            print(")", end="")
        if cnt > 0:
            cnt -= 1

Solution (Python):
if __name__ == "__main__":
    N = int(input())
    S = input()

    l_count = 0
    r_count = 0
    shift = 0
    for i in range(len(S)):
        if S[i + shift] == '(':
            l_count += 1
        else:
            r_count += 1

        if r_count > l_count:
            S = '(' + S
            l_count += 1
            shift += 1

    if l_count > r_count:
        n = l_count - r_count
        S = S + ')' * n

    print(S)

Solution (Python):

import re

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

inputS = S


for _ in range(50): 
    if "()" in S:
        S = S.replace("()","").strip()
    else:
        break
        




insertS = S.translate(str.maketrans({'(': ')', ')': '('}))


ans = inputS.split()


for insert_bracket in insertS:
    if insert_bracket == "(":
        ans.insert(0,"(")
    else:
        ans.append(")")
        
print(''.join(map(str, ans)))

Solution (Python):
import sys
import heapq
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
s = S()
kakko = ["(", ")"]

cnt = 0
for i in range(N):
  if s[i] == kakko[0]:
    cnt += 1
  else:
    cnt = max(cnt-1, 0)
right = cnt

cnt = 0
for i in range(N-1,-1,-1):
  if s[i] == kakko[1]:
    cnt += 1
  else:
    cnt = max(cnt-1, 0)
left = cnt

print(kakko[0]*left + s + kakko[1]*right)

Solution (Python):
import itertools
import math
N = int(input())
S = input()
cot = 0
left_count = 0
for c in S:
    if c == ")":
        if cot > 0:
            cot -=1
        else:
            left_count += 1
    else:
        cot += 1
print("(" * left_count + S + cot * ")")

Solution (Python):

import sys


def solve(N: int, S: str):
    from collections import deque
    d = deque(list(S))
    st = 0
    ad = deque()

    while(len(d)):
        t = d.pop()
        if t == ')':
            ad.appendleft(t)
            st += 1
        else:
            if(st > 0):
                st -= 1
            else:
                ad.append(')')

            ad.appendleft('(')
                    
    ad.appendleft('(' * st)
        
    print(''.join(ad))

    return



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

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
s = input()
max1 = 0
cnt1 = 0
for c in s:
    cnt1 += 1 if c == ')' else - 1
    max1 = max(max1, cnt1)
s = '(' * max1 + s

max2 = 0
cnt2 = 0
for c in reversed(s):
    cnt2 += 1 if c == '(' else - 1
    max2 = max(max2, cnt2)
s = s + ')' * max2

print(s)

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

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

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

for i in range(left_max):
    s = '(' + s
for i in range(right_max):
    s = s + ')'
print(s)

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

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

L=0
R=0

for i in range(N):
    if(S[i]=="("):
        R+=1
 
    elif(S[i]==")"):
        if(R==0):
            L+=1
        else:
            R-=1

for i in range(R):
        S.append(")")

for i in range(L):
    S.insert(0,"(")
    
print("".join(S))

Solution (Python):
n=int(input())
s=input()
cnt=0
M=0

for i in s:
    if i==")":
        cnt+=1
    else:
        cnt-=1
    M=max(M,cnt)

print("("*M+s+")"*(M-cnt))

Solution (Python):
def resolve():
    n = int(input())
    s = input()
    l, r = 0, 0
    for c in s:
        if c == "(":
            l += 1
        elif l > 0 and c == ")":
            l -= 1
    for c in s[::-1]:
        if c == ")":
            r += 1
        elif r > 0 and c == "(":
            r -= 1
    ans = "(" * r + s + ")" * l
    print(ans)


if __name__ == "__main__":
    resolve()

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

cnt1=0
cnt2=0


for i in range(N):
    if S[i]=="(":
        cnt1+=1
    else:
        if cnt1>0:
            cnt1-=1
        else:
            cnt2+=1

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

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

temp=list(S)
f=True

while f :
    f=False
    L=len(temp)
    for i in range(L-2,-1,-1):
        if  "".join(temp[i:i+2])=="()":
            temp.pop(i+1)
            temp.pop(i)
            f=True

Ltemp=len(temp)
if Ltemp==0:
    print(S)
    exit()
    
if temp[0]=="(":
    add=")"*len(temp)
    ans=S+add
else:
    cnt1=0
    cnt2=0
    for i in range(Ltemp):
        if temp[i]==")":
            cnt1+=1
        else:
            cnt2+=1
        add1="("*cnt1
        add2=")"*cnt2
    ans=add1+S+add2


print(ans)

Solution (Python):

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

T = S.copy()

flag = False




for i in range(N):
    flag = False
    i = 0
    while True:
        if i > len(S) - 1:
            break
        if S[i] == '(':
            tmp = i
            flag = True
        if flag and S[i] == ')':
            S.pop(i)
            S.pop(tmp)
            flag = False
        i += 1




a = S.count('(')
b = S.count(')')

ans = '('*b + ''.join(T) + ')'*a
print(ans)

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

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

Solution (Python):
import copy
N = int(input())
S = input()
SS = list(copy.deepcopy(S))
cnt = 0
for i in range(N):
  if S[i] == "(":
    cnt += 1
  else:
    cnt -= 1
  if cnt < 0:
    SS.insert(0,"(")
    cnt = 0
if cnt > 0:
  for j in range(cnt):
    SS.append(")")
print(*SS,sep="")

Solution (Python):
n = int(input())
s = input()
l = s.count("(")
r = s.count(")")
lmax = 0
if n == 1:
    print("()")
elif l == 0:
    print("("* r + s)
elif r == 0:
    print(s + ")"*l)
else:
    l = 0
    r = 0
    for c in s:
        if c == "(":
            l += 1
        else:
            r += 1
        lmax = max(r-l, lmax,0)
    
    res = "(" * lmax + s 

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

    if l > r:
        res = res + ")" * (l-r)

    elif r > l:
        res = "(" * (r-l) + res

    print(res)

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

l, r = [], []

for i in range(n):
    if s[i] == '(':
        l.append(i)
    else: r.append(i)

for rv in r[:]:
    if not l: break
    if rv > l[0]:
        r.remove(rv)
        del l[0]

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

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

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

left = tmp.count(")")
right = tmp.count("(")
ans = "(" * left + s + ")" * right
print(ans)

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

c = N
SS = S
while (c > 0):
  SS = SS.replace('()','')
  c = SS.count('()')
print('(' * SS.count(')') + S + ')' * SS.count('('))

Solution (Python):

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

rnum = 0
lnum = 0

for i in S:
  if i == ")":
    if lnum > 0:
      lnum -= 1
    else:
      rnum += 1
  
  else:
    lnum += 1
    
ans = ""

for i in range(rnum):
  ans += "("
ans += S

for i in range(lnum):
  ans += ")"
  
print (ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce



sys.setrecursionlimit(2147483647)
INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
s = S()
l = 0
r = 0
for i in s:
    if i == ')':
        if l:
            l -= 1
        else:
            r += 1
    else:
        l += 1



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

Solution (Python):
n = int(input())
s = input().rstrip()
remaining_l = 0
remaining_r = 0
index = 0
while index < n:
    left = right = 0
    while index < n and s[index] == '(':
        left += 1
        index += 1
    while index < n and s[index] == ')':
        right += 1
        index += 1
    if left > right:
        remaining_r += left - right
    elif left < right:
        k = right - left
        if remaining_r <= k:
            remaining_l += k - remaining_r
            remaining_r = 0
        else:
            remaining_r -= k
print('(' * remaining_l + s + ')' * remaining_r)

Solution (Python):
n = int(input())
s = input()
l = 0
ans = ""
for e in s:
  if e==')':
    if l<=0:
      ans += '('
    else:
      l -= 1
  else:
    l += 1
print(ans + s + ')'*l)

Solution (Python):

from collections import deque

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

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

cnt=0
cntL=0

def solve(w,r,s):
    cnt=0
    res=0
    for i in range(n):
        if s[i]==w:
            if cnt:
                cnt-=1
            else:res+=1
        else:
            cnt+=1    
    return list(r*res)




pre=solve(')','(',s)
suf=solve('(',')',s[::-1])
ans=pre+s+suf
print(''.join(ans))

Solution (Python):
from sys import stdin, exit
N = int(stdin.readline().rstrip())
S = stdin.readline().rstrip()
count, l, r = 0, 0, 0

for i in range(len(S)):
    if S[i] == '(':
        count += 1
    else:
        if count == 0:
            l += 1
        else:
            count -= 1
r = count
ans = ""
for i in range(l):
    ans += '('
ans += S
for i in range(r):
    ans += ')'
print(ans)

Solution (Python):
N = int(input())
S = input()
cnt_l = 0
cnt_r = 0
for s in S:
    if s == '(':
        cnt_l += 1
    else:
        if cnt_l > 0:
            cnt_l -= 1
        else:
            cnt_r += 1
print('('*cnt_r+S+')'*cnt_l)

Solution (Python):
n=int(input())
s=list(input())
l=[]
ctl=0;ctr=0
for i in range(n):
  if s[i]=='(':
    ctl+=1
  else:
    ctr+=1
  if ctl<ctr:
    l.append('(')
    ctl+=1
l.reverse()
for i in range(ctl-ctr):
  s.append(')')
s=l+s
print(''.join(s))

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

def main():
    _ = int(input())
    S = input().strip()
    ans = ""
    l = r = 0
    for c in S:
        if c == "(":
            r += 1
        elif c == ")":
            if r > 0:
                r -= 1
            else:
                l += 1
    ans = "("*l + S + ")"*r
    print(ans)

if __name__ == '__main__':
    main()

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

l_cnt = 0
res = ''

for s in S:
    if s == '(':
        l_cnt += 1
        res += s
    else:
        if l_cnt == 0:
            res = '(' + res
        else:
            l_cnt -= 1
        res += s

res += ')' * l_cnt

print(res)

Solution (Python):
N = int(input())
S = input()
count = 0
flag = 0
while flag == 0:
    flag = 1
    dep = 0
    for i in S:
        if i == ")":
            dep += 1
        else:
            dep -= 1
        if dep > 0:
            break
    if dep > 0:
        S = "("*dep + S
        flag = 0
    elif dep < 0:
        S = S + ")"*(-dep)
        flag = 0
    
print(S)

Solution (Python):
import sys
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def S(): return input()

def main():
    N = I()
    s = S()
    Left = ""

    countO = 0
    for x in s:
        if x==")" and countO == 0:
            Left = "("+Left
        elif x==")":
            countO -= 1
        elif x=="(":
            countO += 1
    return(Left+s+")"*countO)


if __name__ == "__main__":
    print(main())

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

left = 0
leftplus = 0
for i in range(len(s)):
    if s[i] == '(':
        left += 1
    else:
        if left == 0:
            leftplus += 1
        else:
            left -= 1

right = 0
rightplus = 0
r = s[::-1]
for i in range(len(r)):
    if r[i] == ')':
        right += 1
    else:
        if right == 0:
            rightplus += 1
        else:
            right -= 1
print('('*leftplus + s + ')'*rightplus)

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

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

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

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

N, = map(int, input().split())
S = list(input().strip())

lc = 0
rc = 0

for i in range(N):
    t = S[i]

    if t == ")":
        if lc > 0:
            lc -= 1
        else:
            rc += 1
    else:
        lc += 1

print("(" * rc + "".join(S) + ")" * lc)

Solution (Python):
import copy
n=int(input())
s=input()
ans=copy.deepcopy(s)
paren=0
for i in range(n):
    if(s[i] == '('):
        paren+=1
    elif(paren <= 0):
        ans = "(" + ans
    else:
        paren-=1

for i in range(paren):
    ans = ans + ")"

print(ans)

Solution (Python):
N = int(input())
S = input()
s = S[:]
while "()" in s:
  s = s.replace("()", "")
r = s.count("(")
l = s.count(")")
print("(" * l + S + ")" * r)

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

Solution (Python):
input();S=input();d=m=0
for c in S:
 if c=="(":d-=1
 else:d+=1
 m=max(d,m)
S="("*m+S;d=m=0
for c in S[::-1]:
 if c=="(":d+=1
 else:d-=1
 m=max(d,m)
print(S+")"*m)

Solution (Python):
def solve(S):
    

    pendings = 0
    prefix = 0
    for c in S:
        if c == '(':
            pendings += 1
        elif c == ')':
            pendings -= 1
        if pendings < 0:
            pendings = 0
            prefix += 1
    answer = '('*prefix + S
    if pendings > 0:
        answer += ')'*(pendings)
    print(answer)

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

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





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


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

print('('*ans_r + S + ')'*ans_l)

Solution (Python):
N=int(input())
S=input()
S3=[]
for i in range(len(S)):
  S3.append(S[i])
  if S3.count("(") < S3.count(")") :
    S3 =["("] + S3
  if i == len(S) - 1:
    for j in range(S3.count("(") - S3.count(")")):
      S3.append(")")
      
print("".join(S3))

Solution (Python):
N = int(input())
S = input()
T = []
c = 0
m = 0
for s in S:
  if s == ")":
    c += 1
  else:
    if c > 0:
      m += c 
      c = 0
    c -= 1
  if c > 0:
    m += c 
    c = 0
print("("*m + S + ")"*(-c))

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

def main():
    N = int(input())
    s = input().strip()
    stock_l = 0
    left = ""
    right = ""
    for i in range(N):
        if s[i] == "(":
            stock_l += 1
        else:
            if stock_l > 0:
                stock_l -= 1
            else:
                left += "("
    print(left + s + ")" * stock_l)



if __name__ == "__main__":
    main()

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
            continue
        r-=1
print("("*l+s+")"*r)

Solution (Python):
def main():

    N = int(input())
    S = input()
    count = 0
    t = ""
    for c in S:
        if c == "(":
            count += 1
        else:
            count -= 1

        if count == -1:
            t = "(" + t + c
            count += 1
        else:
            t += c
    t += ")" * count
    return t


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

Solution (Python):

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

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

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

Solution (Python):
n=int(input())
s=input()
a=b=0
k=0
for i in range(n):
	if s[i]=="(":
		a+=1
	else:
		b+=1
	if a<b:
		k+=1
		a+=1
s=k*("(")+s
if a>b:
	s+=")"*(a-b)
print(s)

Solution (Python):
N = int(input())
S = input()
left=[]
right=[]
for c in S:
    if c == ')':
        if not right:
            left.append('(')
        else:
            right.pop()
    elif c == '(':
        right.append(')')
print(''.join(left) + S + ''.join(right))