| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 45 | 22 | 22 | 61.111% |
There are 2ドルn$ elements divided into $n$ pairs.
For each pair, you should either assign an opening bracket to both elements, or closing bracket to both elements. You need to make the resulting sequence of brackets a correct bracket sequence or determine that it is impossible. If there are several possible solutions, find the solution with the smallest lexicographically string (of 2ドルn$ brackets, '(' is smaller than ')').
The first line contains one integer $n$ (1ドル \leq n \leq 200,000円$).
The next line contains 2ドルn$ integers, $p_1, p_2, \ldots, p_{2n}$ (1ドル \leq p_i \leq n$). All integers from 1ドル$ to $n$ appear exactly two times in this sequence.
If it is impossible to choose one type of bracket for each pair to make the derived bracket sequence correct, print "(" (Russian sad smiley). Otherwise, print the desired lexicographically minimal correct bracket sequence.
2 1 2 1 2
()()
1 1 1
(
4 4 3 1 2 3 2 1 4
(
4 3 1 2 1 4 3 2 4
(()()())
4 2 4 3 1 3 4 2 1
()()()()
4 4 4 3 3 1 2 1 2
(((())))
4 1 3 1 2 4 4 2 3
()(())()