/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 400 点
問題文
( と ) で構成される N 文字の文字列 S が与えられる。S にいくつかの ( または ) を挿入することで正しい括弧列を作りたい。
ただし、正しい括弧列は次のように定義されている：
()は正しい括弧列である。- X が正しい括弧列であるとき、
(、X、)をこの順につなげたものは正しい括弧列である。 - X、Y が正しい括弧列であるとき、X と Y をこの順につなげたものは正しい括弧列である。
- それ以外の括弧列は正しくない。
そのとき、作れる最も文字数が少ない正しい括弧列を求めなさい。このようなものが複数ある場合は、辞書順最小のものを求めなさい。
制約
- S の長さは N である。
- 1 ≤ N ≤ 100
- S は
(と)のみで構成されている。
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
S から (、) を挿入していったときに作れる最小の長さの正しい括弧列のなかで辞書順最小の文字列を出力しなさい。
入力例 1
3 ())
出力例 1
(())
入力例 2
6 )))())
出力例 2
(((()))())
入力例 3
8 ))))((((
出力例 3
(((())))(((())))
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
(((())))(((())))