Score : 400 points
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.(
, X and )
in this order is also a correct bracket sequence.Find the shortest correct bracket sequence that can be obtained. If there is more than one such sequence, find the lexicographically smallest one.
(
and )
.Input is given from Standard Input in the following format:
N S
Print the lexicographically smallest string among the shortest correct bracket sequences that can be obtained by inserting some number of (
and )
into S.
3 ())
(())
6 )))())
(((()))())
8 ))))((((
(((())))(((())))