← 返回题目列表

AtCoder · abc064_d

D. 插入

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给你一个字符串 S 长度 N 组成 ( 和 )。你的任务是插入一些 ( 和 ) 进入 S 获得 正确的括号顺序.
这里,正确的括号序列定义如下:

  • () 是正确的括号序列。
  • If X 是正确的括号序列,串联 (, X 和 ) 这个顺序也是正确的括号顺序。
  • If X 和 Y 是正确的括号序列,串联 X 和 Y 这个顺序也是正确的括号顺序。
  • 每个正确的括号序列都可以从上述规则中推导出来。

找出可获得的最短正确括号序列。如果存在多个这样的序列,请找到字典顺序最小的一个。

约束

  • 的长度 S is N.
  • 1 ≤ N ≤ 100
  • S 包括 ( 和 ).

输入

输入由标准输入按以下格式给出:

N
S

输出

打印最短的正确括号序列中按字典顺序排列的最小字符串,该序列可以通过插入一定数量的 ( 和 ) 进入 S.


示例输入 1

3
())

示例输出 1

(())

示例输入 2

6
)))())

示例输出 2

(((()))())

示例输入 3

8
))))((((

示例输出 3

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