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

(((())))(((())))



Sample input:
3
())


Sample output:
(())

Submission status: Wrong Answer

Solution code:
import sys


def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    for i in range(n):
        if s[i] == ')':
            continue
        else:
            i_l = i
            break
    else:
        i_l = n
    for i in range(n, 0, -1):
        if s[i-1] == '(':
            continue
        else:
            i_r = i
            break
    else:
        i_r = 0

    res_l = '(' * len(s[:i_l]) + s[:i_l]
    res_r = s[i_r:] + ')' * len(s[i_r:])
    
    c = s[i_l:i_r]



    count = c.count('(') - c.count(')')
    if count == 0:
        ans = res_l + c + res_r
    elif count < 0:
        ans = '(' * abs(count) + res_l + c + res_r
    else:
        ans = res_l + c + res_r + ')' * count
    print(ans)
    # s = '.' + s
    
    # # 左右から一度ずつチェック
    # # 左から
    # count = 0
    # flag = False
    # for i in range(1, len(s)):
    #     if s[i] == ')':
    #         if not flag:
    #             count += 1
    #         else:
    #             flag = False
    #     elif s[i] == '(':
    #         if s[i-1] == '.':
    #             count -= 1
    #         elif s[i-1] == ')':
    #             flag = True
    #         elif s[i-1] == '(':
    #             if not flag:
    #                 count -= 1
    #             else:
    #                 break
    
    # s = s.replace('.', '') + '.'
    # if count >= 1:
    #     s = '(' * count + s


    # count = 0
    # flag = False
    # for i in range(len(s)-2, -1, -1):
    #     if s[i] == '(':
    #         if not flag:
    #             count += 1
    #         else:
    #             flag = False
    #     elif s[i] == ')':
    #         if s[i+1] == '.':
    #             count -= 1
    #         elif s[i+1] == '(':
    #             flag = True
    #         elif s[i+1] == ')':
    #             if not flag:
    #                 count -= 1
    #             else:
    #                 break
    #     print(count)
    
    # s = s.replace('.', '')
    # if count >= 1:
    #     s = s + ')' * count

    # print(s)

            

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    for i in range(n):
        if s[i] == ')':
            continue
        else:
            i_l = i
            break
    else:
        i_l = n
    for i in range(n, 0, -1):
        if s[i-1] == '(':
            continue
        else:
            i_r = i
            break
    else:
        i_r = 0

    res_l = '(' * len(s[:i_l]) + s[:i_l]
    res_r = s[i_r:] + ')' * len(s[i_r:])
    
    c = s[i_l:i_r]
    print(res_l, c, res_r)


    count = c.count('(') - c.count(')')
    if count == 0:
        ans = res_l + c + res_r
    elif count < 0:
        ans = '(' * abs(count) + res_l + c + res_r
    else:
        ans = res_l + c + res_r + ')' * count
    print(ans)
    # s = '.' + s
    
    # # 左右から一度ずつチェック
    # # 左から
    # count = 0
    # flag = False
    # for i in range(1, len(s)):
    #     if s[i] == ')':
    #         if not flag:
    #             count += 1
    #         else:
    #             flag = False
    #     elif s[i] == '(':
    #         if s[i-1] == '.':
    #             count -= 1
    #         elif s[i-1] == ')':
    #             flag = True
    #         elif s[i-1] == '(':
    #             if not flag:
    #                 count -= 1
    #             else:
    #                 break
    
    # s = s.replace('.', '') + '.'
    # if count >= 1:
    #     s = '(' * count + s


    # count = 0
    # flag = False
    # for i in range(len(s)-2, -1, -1):
    #     if s[i] == '(':
    #         if not flag:
    #             count += 1
    #         else:
    #             flag = False
    #     elif s[i] == ')':
    #         if s[i+1] == '.':
    #             count -= 1
    #         elif s[i+1] == '(':
    #             flag = True
    #         elif s[i+1] == ')':
    #             if not flag:
    #                 count -= 1
    #             else:
    #                 break
    #     print(count)
    
    # s = s.replace('.', '')
    # if count >= 1:
    #     s = s + ')' * count

    # print(s)

            

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


def main():
    n, s = sys.stdin.read().split()

    s = '.' + s
    
    # 左右から一度ずつチェック
    # 左から
    count = 0
    flag = False
    for i in range(1, len(s)):
        if s[i] == ')':
            if not flag:
                count += 1
            else:
                flag = False
        elif s[i] == '(':
            if s[i-1] == '.':
                count -= 1
            elif s[i-1] == ')':
                flag = True
            elif s[i-1] == '(':
                if not flag:
                    count -= 1
                else:
                    break
    
    s = s.replace('.', '') + '.'
    if count >= 1:
        s = '(' * count + s


    count = 0
    flag = False
    for i in range(len(s)-2, -1, -1):
        if s[i] == '(':
            if not flag:
                count += 1
            else:
                flag = False
        elif s[i] == ')':
            if s[i+1] == '.':
                count -= 1
            elif s[i+1] == '(':
                flag = True
            elif s[i+1] == ')':
                if not flag:
                    count -= 1
                else:
                    break
    
    s = s.replace('.', '')
    if count >= 1:
        s = s + ')' * count

    print(s)

            

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


def main():
    n, s = sys.stdin.read().split()

    s = '.' + s
    
    # 左右から一度ずつチェック
    # 左から
    count = 0
    flag = False
    for i in range(1, len(s)):
        if s[i] == ')':
            if not flag:
                count += 1
            else:
                flag = False
        elif s[i] == '(':
            if s[i-1] == '.':
                count -= 1
            elif s[i-1] == ')':
                flag = True
            elif s[i-1] == '(':
                if not flag:
                    count -= 1
                else:
                    break
    
    s = s.replace('.', '') + '.'
    if count >= 1:
        s = '(' * count + s


    count = 0
    flag = False
    for i in range(len(s)-2, -1, -1):
        if s[i] == '(':
            if not flag:
                count += 1
            else:
                flag = False
        elif s[i] == ')':
            if s[i-1] == '.':
                count -= 1
            elif s[i-1] == '(':
                flag = True
            elif s[i-1] == ')':
                if not flag:
                    count -= 1
                else:
                    break
    
    s = s.replace('.', '')
    if count >= 1:
        s = s + ')' * count
        
    print(s)

            

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys


def main():
    n, s = sys.stdin.read().split()
    
    # 左右から一度ずつチェック
    # 左から
    count = 0
    flag = False
    for i in range(len(s)):
        if s[i] == ')':
            if not flag:
                count += 1
            else:
                flag = False
                continue
        else:
            if not flag:
                flag = True
            else:
                break
    
    s = '(' * count + s

    # 右から
    count = 0
    flag = False
    for i in range(len(s)-1, -1, -1):
        if s[i] == '(':
            if not flag:
                count += 1
            else:
                flag = False
                continue
        else:
            if not flag:
                flag = True
            else:
                break

    s = s + ')' * count

    print(s)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
left,right=0,0
add=[]
for i in range(1,n):
    if s[i-1]+s[i]==")(":
        add.append(i)

add +=[n]
point=0
words=[]
for i in add:
    words.append(s[point:i])
    point=i

for i in words:
    left_one=i.count(")")
    right_one=i.count("(")
    if left_one>=right_one:
        left +=left_one-right_one
    else:
        right +=right_one-left_one

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

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
s = input()
d = deque(s)

stack = []
for c in s:
  #抜き出したもの(c)が左括弧だった場合
  if c == "(":
    stack.append(c)
    
  #抜き出したもの(c)が右括弧だった場合
  else:
    #stackがなかった場合
    if not stack:
      d.appendleft('(')
      
    #stackがあった場合
    else:
      #末尾をstackから削除しつつ、その末尾のものをtopと定義する
      stack.pop()
print("".join(list(d)))

Submission status: Wrong Answer

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

if s[0] == ')':
    s = '(' + s
if s[-1] == '(':
    s += ')'

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

print(result)

Submission status: Wrong Answer

Solution code:
from collections import Counter

N = int(input())
S = input()
cnt = 0
for s in S:
  if s == ')': cnt += 1
  else:break
S = '('*cnt + S

cnt = 0
for s in S[::-1]:
  if s == '(': cnt += 1
  else:break
S = S + ')'*cnt 

Scnt = Counter(S)
if Scnt['('] < Scnt[')']:
  print('('*(Scnt[')']-Scnt['('])+S)
elif Scnt[')'] < Scnt['(']:
  print(S+')'*(Scnt['(']-Scnt[')']))
else:
  print(S)

Submission status: Wrong Answer

Solution code:
N = int(input())
s = input()
r = 0
c = 0
sw = True
for i in range(N):
    if s[i] == '(':
        sw = False
        c += 1
    elif sw:
        r += 1
    else:
        c -= 1
    # print(r, c)

if c > 0:
    ans = '(' * r + s + ')' * c
else:
    ans = '(' * (r - c) + s
print(ans)

Submission status: Wrong Answer

Solution code:
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 range(len(r)):
        if r[i] < max(l):
            cnt += 1
            l.pop(-1)
    print((len(l)) * "(" + s + (len(r) - cnt) * ")")

Submission status: Wrong Answer

Solution code:

bl = 0
br = 0

def solve(s):
    l = 0
    r = 0
    global bl,br
    for i in range(len(s)):
        if s[i] == "(":
            l += 1
        else:
            r += 1
    if l - r > 0:
        br += l-r
    elif r - l > 0:
        bl += r-l
    #print(br,bl)

n = int(input())
nodes = [0]
brackets = []
s = input()
for i in range(len(s)-1):
    if s[i] == ")" and s[i+1] == "(":
        nodes.append(i+1)
#print(nodes)
for i in range(len(nodes)-1):
    brackets.append(s[nodes[i]:nodes[i+1]])
brackets.append(s[nodes[-1]:])
#print(brackets)

for i in brackets:
    solve(i)
    #print(br,bl)
ans = "("*bl + s +")"*br
print(ans)

Submission status: Wrong Answer

Solution code:
def solve(s):
    l = 0
    r = 0
    for i in range(len(s)):
        if s[i] == "(":
            l += 1
        else:
            r += 1
    if l - r > 0:
        ans = s+")"*(l-r)
    elif r - l > 0:
        ans = "("*(r-l) + s
    else:
        ans = s
    return ans


n = int(input())
s = str(input())
l = 0
r = 0
for i in range(len(s)):
    if s[i] == "(":
        l += 1
    else:
        r += 1
if l - r > 0:
    ans = s+")"*(l-r)
elif r - l > 0:
    ans = "("*(r-l) + s
else:
    nodes = [0]
    brackets = []
    for i in range(len(s)-1):
        if s[i] == ")" and s[i+1] == "(":
            nodes.append(i+1)
    #print(nodes)
    for i in range(len(nodes)-1):
        brackets.append(s[nodes[i]:nodes[i+1]])
    brackets.append(s[nodes[-1]:])
    #print(brackets)
    ans = ""
    for i in brackets:
        ans += solve(i)
print(ans)

Submission status: Wrong Answer

Solution code:
def solve(s):
    l = 0
    r = 0
    for i in range(len(s)):
        if s[i] == "(":
            l += 1
        else:
            r += 1
    if l - r > 0:
        ans = s+")"*(l-r)
    elif r - l > 0:
        ans = "("*(r-l) + s
    else:
        ans = s
    return ans


n = int(input())
nodes = [0]
brackets = []
s = input()
for i in range(len(s)-1):
    if s[i] == ")" and s[i+1] == "(":
        nodes.append(i+1)

for i in range(len(nodes)-1):
    brackets.append(s[nodes[i]:nodes[i+1]])
brackets.append(s[nodes[-1]:])

AnsStr = ""
for i in brackets:
    AnsStr += solve(i)
print(AnsStr)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
B=[1]
for i in range(1,N):
    if S[i]==S[i-1]:
        B[-1]+=1
    else:
        B.append(1)

if S[0]==')':
    S='('*B[0]+S
    B.insert(0,B[0])
if S[-1]=='(':
    S=S+')'*B[-1]
    B.append(B[-1])

for i in range(len(B)//2):
    if B[2*i]>B[2*i+1]:
        a=B[2*i]-B[2*i+1]
        S=S+')'*a
    elif B[2*i]<B[2*i+1]:
        b=B[2*i+1]-B[2*i]
        S='('*b+S

print(S)

Submission status: Wrong Answer

Solution code:
#insertion
n=int(input())
s=input()
count=1
countlist=[]
s=s+"X"
for i  in range(n):
    if s[i]==s[i+1]:
        count+=1
    else:
        if s[i]=="(":
            countlist.append((count,"L"))
        else:
            countlist.append((count,"R"))
        count=1

if len(countlist)%2==0 and countlist[0][1]=="L":
    pass
elif len(countlist)%2!=0 and countlist[0][1]=="L":
    countlist.append((countlist[-1][0],"R"))
elif len(countlist)%2==0 and countlist[0][1]=="R":
    countlist.append((countlist[-1][0],"R"))
    countlist=[(countlist[0][0],"L")]+countlist
elif len(countlist)%2!=0 and countlist[0][1]=="R":
    countlist=[(countlist[0][0],"L")]+countlist

ans=""
for i in range(0,len(countlist),2):
    x=max(countlist[i][0],countlist[i+1][0])
    ans=ans+"("*x+")"*x
print(ans)

Submission status: Wrong Answer

Solution code:
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(s)
print(''.join(s))

Submission status: Wrong Answer

Solution code:
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(*s)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
cnt=[1 if S[0]=='(' else -1]
for c in S[1:]:
    cnt.append(cnt[-1]+(1 if c=='(' else -1))
d=-min(cnt)
if d>0:
    S='('*d+S+')'*(cnt[-1]+d)
print(S)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
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 i == N - 1 or (S[i] == ")" and S[i + 1] == "("):
        # )(だったら
        sub_s += ch
        counter = collections.Counter(sub_s)
        if counter["("] > counter[")"]:
            ext_n_open += counter["("] - counter[")"]
        elif counter["("] < counter[")"]:
            n_close_w = counter[")"] - counter["("]
            n_close = max(0, n_close_w - ext_n_open)
            ext_n_open = max(0, ext_n_open - n_close_w)
            ext_n_close += n_close
        sub_s = ""
    else:
        # )), ((, ()
        sub_s += ch

if ext_n_open < ext_n_close:
    ans = "(" * (ext_n_close - ext_n_open) + S
elif ext_n_open > ext_n_close:
    ans = S + ")" * (ext_n_open - ext_n_close)
else:
    ans = "(" * ext_n_open + S + ")" * ext_n_close

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
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 i == N - 1 or (S[i] == ")" and S[i + 1] == "("):
        # )(だったら
        sub_s += ch
        counter = collections.Counter(sub_s)
        ext_n_open += max(0, counter["("] - counter[")"])
        ext_n_close += max(0, counter[")"] - counter["("])
        sub_s = ""
    else:
        # )), ((, ()
        sub_s += ch

if ext_n_open < ext_n_close:
    ans = "(" * (ext_n_close - ext_n_open) + S
elif ext_n_open > ext_n_close:
    ans = S + ")" * (ext_n_open - ext_n_close)
else:
    ans = "(" * ext_n_open + S + ")" * ext_n_close

print(ans)

Submission status: Wrong Answer

Solution code:
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 
L += ')' * abs(acc[-1] - x)
print(L)

Submission status: Wrong Answer

Solution code:
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 = list(input())
l = 0
r = 0
L = ''
last = 0
tmp = ''
for i in range(n):
    if s[i] == '(':
        l += 1
        tmp += '('
    else:
        r += 1
        tmp += ')'
        if i == n-1:
            continue
        if s[i+1] == '(':
            if l > r:
                last += (l-r)
            elif l < r:
                L = '(' * (r-l) + L
            L += tmp
            tmp = ''
            l = 0
            r = 0

if l > r:
    last += l-r
elif l < r:
    L = '(' * (r-l) + L
L += tmp
L += ')' * last
print(L)

Submission status: Wrong Answer

Solution code:
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 = list(input())
l = 0
r = 0
L = ''
tmp = ''
for i in range(n):
    if s[i] == '(':
        l += 1
        tmp += '('
    else:
        r += 1
        tmp += ')'
        if i == n-1:
            continue
        if s[i+1] == '(':
            if l > r:
                tmp += ')' * (l-r)
            elif l < r:
                L = '(' * (r-l) + L
            L += tmp
            tmp = ''
            l = 0
            r = 0

if l > r:
    tmp += ')' * (l-r)
elif l < r:
    L = '(' * (r-l) + L
L += tmp

print(L)

Submission status: Wrong Answer

Solution code:
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)
print(l,m,r)
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)+w)

Submission status: Wrong Answer

Solution code:
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))
    else:
      print("("*(r-l-m)+w)

Submission status: Wrong Answer

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

def add(lft,rgt,cnt):
    for k in range(lft):
        ans.append("(")
    if cnt > 0:
        for k in range(cnt):
            ans.append(")")
    else:
        for k in range(abs(cnt)):
            ans.append("(")
    for k in range(rgt):
        ans.append(")")
        cnt = 1
    


ans = []
cnt = 0
cnt2 = 0
cnt3 = 0
lft = 0
rgt = 0

if s[0] == "(":
    cnt += 1
    lft += 1
elif s[0] == ")":
    cnt -= 1
    rgt += 1



for i in range(1,n):
    if s[i-1]==")" and s[i] == "(":
        

        if cnt >= 0:
            add(lft,rgt,0)
            cnt3 += cnt
        elif cnt < 0:
            add(lft,rgt,0)
            cnt2 += cnt
        
        lft = 0
        cnt = 0
        rgt = 0
        
    if s[i] == "(":
        cnt += 1
        lft += 1
    elif s[i] == ")":
        cnt -= 1
        rgt += 1


if cnt >= 0:
    add(lft,rgt,0)
    cnt3 += cnt
elif cnt < 0:
    add(lft,rgt,0)
    cnt2 += cnt



ans2 = ""

for i in range(len(ans)):
    ans2 += ans[i]

if cnt2 <0:
    for i in range(-cnt2):
        ans2 = "("+ans2
if cnt3 >0:
    for i in range(cnt3):
        ans2 += ")"

print(ans2)

Submission status: Wrong Answer

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

def add(lft,rgt,cnt):
    for k in range(lft):
        ans.append("(")
    if cnt > 0:
        for k in range(cnt):
            ans.append(")")
    else:
        for k in range(abs(cnt)):
            ans.append("(")
    for k in range(rgt):
        ans.append(")")
        cnt = 1
    


ans = []
cnt = 0
cnt2 = 0
cnt3 = 0
lft = 0
rgt = 0

if s[0] == "(":
    cnt += 1
    lft += 1
elif s[0] == ")":
    cnt -= 1
    rgt += 1



for i in range(1,n):
    if s[i-1]==")" and s[i] == "(":
        

        if cnt >= 0:
            add(lft,rgt,cnt)
            cnt3 += cnt
        elif cnt < 0:
            add(lft,rgt,0)
            cnt2 += cnt
        
        lft = 0
        cnt = 0
        rgt = 0
        
    if s[i] == "(":
        cnt += 1
        lft += 1
    elif s[i] == ")":
        cnt -= 1
        rgt += 1


if cnt >= 0:
    add(lft,rgt,cnt)
    cnt3 += cnt
elif cnt < 0:
    add(lft,rgt,0)
    cnt2 += cnt



ans2 = ""

for i in range(len(ans)):
    ans2 += ans[i]

if cnt2 <0:
    for i in range(-cnt2):
        ans2 = "("+ans2
if cnt3 >0:
    for i in range(cnt3):
        ans2 += ")"

print(ans2)

Submission status: Wrong Answer

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

def add(lft,rgt,cnt):
    for k in range(lft):
        ans.append("(")
    if cnt > 0:
        for k in range(cnt):
            ans.append(")")
    else:
        for k in range(abs(cnt)):
            ans.append("(")
    for k in range(rgt):
        ans.append(")")
        cnt = 1
    


ans = []
cnt = 0
cnt2 = 0
lft = 0
rgt = 0

if s[0] == "(":
    cnt += 1
    lft += 1
elif s[0] == ")":
    cnt -= 1
    rgt += 1



for i in range(1,n):
    if s[i-1]==")" and s[i] == "(":
        

        if cnt >= 0:
            add(lft,rgt,cnt)
        elif cnt < 0:
            add(lft,rgt,0)
            cnt2 += cnt
        
        lft = 0
        cnt = 0
        rgt = 0
        
    if s[i] == "(":
        cnt += 1
        lft += 1
    elif s[i] == ")":
        cnt -= 1
        rgt += 1


if cnt >= 0:
    add(lft,rgt,cnt)
elif cnt < 0:
    add(lft,rgt,0)
    cnt2 += cnt



ans2 = ""

for i in range(len(ans)):
    ans2 += ans[i]

if cnt2 <0:
    for i in range(-cnt2):
        ans2 = "("+ans2

print(ans2)

Submission status: Wrong Answer

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

def add(lft,rgt,cnt):
    for k in range(lft):
        ans.append("(")
    if cnt > 0:
        for k in range(cnt):
            ans.append(")")
    else:
        for k in range(abs(cnt)):
            ans.append("(")
    for k in range(rgt):
        ans.append(")")
        cnt = 1


ans = []
cnt = 0
cnt2 = 0
lft = 0
rgt = 0

if s[0] == "(":
    cnt += 1
    lft += 1
elif s[0] == ")":
    cnt -= 1
    rgt += 1



for i in range(1,n):
    if s[i-1]==")" and s[i] == "(":
        if cnt > 0:
            add(lft,rgt,cnt)
        elif cnt < 0:
            add(lft,rgt,0)
            cnt2 += cnt
        
        lft = 0
        cnt = 0
        rgt = 0
        
    if s[i] == "(":
        cnt += 1
        lft += 1
    elif s[i] == ")":
        cnt -= 1
        rgt += 1


if cnt > 0:
    add(lft,rgt,cnt)
elif cnt < 0:
    add(lft,rgt,0)
    cnt2 += cnt


ans2 = ""

for i in range(len(ans)):
    ans2 += ans[i]

if cnt2 <0:
    for i in range(-cnt2):
        ans2 = "("+ans2

print(ans2)

Submission status: Wrong Answer

Solution code:
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:
            r += 1
        else:
            stack.pop()

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

Submission status: Wrong Answer

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
S = (stdin.readline().rstrip())
l = 0
r = 1
l_cnt = 0
r_cnt = 0
for i in range(N):
    if l+r > N:
        break
    if S[l] == "(" and S[-r] == "(":
        r_cnt += 1
        r += 1
    elif S[l] == ")" and S[-r] == ")":
        l_cnt += 1
        l += 1
    elif S[l] == ")" and S[-r] == "(":
        r_cnt += 1
        l_cnt += 1
        r += 1
        l += 1

    elif S[l] == "(" and S[-r] == ")":
        l += 1
        r += 1
print(l_cnt*"(" + S + r_cnt*")")

Submission status: Wrong Answer

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

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

l=0
fl=0
r=0
for i in reversed(range(N)):
  if S[i]=="(":
    l+=1
  else:
    if l>0:
      fl+=max(l-r,0)
      l=0
      r=0
    r+=1
fl+=max(l-r,0)


print("".join(["("]*fr+S+[")"]*fl))

Submission status: Wrong Answer

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

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

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


print("".join(["("]*fr+S+[")"]*fl))

Submission status: Wrong Answer

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

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

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


print("".join(["("]*fr+S+[")"]*fl))

Submission status: Wrong Answer

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

cnt1=0
cnt2=0

if S[0]=="(":
    cnt1+=1
else:
    cnt2+=1

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

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

Submission status: Wrong Answer

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

temp=list(S)

for i in range(N-2,-1,-1):
    if  S[i:i+2]=="()":
        temp.pop(i+1)
        temp.pop(i)

Ltemp=len(temp)
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)

Submission status: Wrong Answer

Solution code:
import sys

N=input()
N=int(N)

A=input()
a=A
a.split()
count=0
p=a.rfind(')');
q=a.find('(');
if(q>0):
    A='('*q+A
if(N-p-1>0):
    A=A+')'*(N-p-1)
for i in range(q,N-(N-p-1)):
    if(a[i]=='('):
        count+=1
    elif(a[i]==')'):
        count-=1
if(count>0):
    A=A+')'*count
elif(count<0):
    A='('*(-count)+A

print(A)

Submission status: Wrong Answer

Solution code:
import sys

N=input()
N=int(N)

A=input()
a=A
a.split()
count=0
p=a.rfind(')');
q=a.find('(');
print(N-p-1)
print(q)
if(q>0):
    A='('*q+A
if(N-p-1>0):
    A=A+')'*(N-p-1)
for i in range(q,N-(N-p-1)):
    if(a[i]=='('):
        count+=1
    elif(a[i]==')'):
        count-=1
if(count>0):
    A=A+')'*count
elif(count<0):
    A='('*(-count)+A

print(A)

Submission status: Wrong Answer

Solution code:
import sys

N=input()
N=int(N)

A=input()
a=A
a.split()
count=0
q=a.find('(');
if(q>0):
    A='('*q+A
for i in range(q,N):
    if(a[i]=='('):
        count+=1
    elif(a[i]==')'):
        count-=1
if(count>0):
    A=A+')'*count
elif(count<0):
    A='('*(-count)+A

print(A)

Submission status: Wrong Answer

Solution code:
import sys

N=input()
N=int(N)

A=input()
a=A
a.split()
count=0
q=a.find('(');
print(q)
if(q>0):
    A='('*q+A
for i in range(q,N):
    if(a[i]=='('):
        count+=1
    elif(a[i]==')'):
        count-=1
print(count)
if(count>0):
    A=A+')'*count
elif(count<0):
    A='('*(-count)+A

print(A)