output_description: Print the lexicographically smallest string among the shortest correct bracket
  sequences that can be obtained by inserting some number of `(` and `)` into S.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      S
attempt: import sys
  
  
  ## io ##
  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()))
  
  
  ## dp ##
  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)]
  
  
  ## math ##
  def to_bin(x: int) -> str:
      return format(x, "b")  # rev => int(res, 2)
  
  
  def to_oct(x: int) -> str:
      return format(x, "o")  # rev => int(res, 8)
  
  
  def to_hex(x: int) -> str:
      return format(x, "x")  # rev => int(res, 16)
  
  
  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]]
  
  
  ## libs ##
  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:
          # print(''.join(dq))
          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()
  
problem_description: 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.
samples: [{"input": "3\n    ())", "output": "(())\n    \n\n* * *"}, {"input": "6\n    )))())", "output": "(((()))())\n    \n\n* * *"}, {"input": "8\n    ))))((((", "output": "(((())))(((())))"}]