Brackets

시간 제한1초메모리 제한512 MB

요약

길이 2n인 수열에서 1부터 n까지의 각 수가 정확히 두 번 나타난다. 같은 수의 두 위치에 같은 괄호를 넣어 올바른 괄호열을 만들되, 사전순으로 가장 작은 것을 구한다.

난이도: 보통10점 중 7점
유형: 그리디, 스택, 구현, 구간
정답자: 아직 제출이 없습니다

문제

There are $2n$ 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 $2n$ brackets, '(' is smaller than ')').

입력

The first line contains one integer $n$ ( $1 \leq n \leq 200\\,000$ ).

The next line contains $2n$ 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.

예제7

예제 1
입력
```
2
1 2 1 2
```
예상 출력
```
()()
```
예제 2
입력
```
1
1 1
```
예상 출력
```
(
```
예제 3
입력
```
4
4 3 1 2 3 2 1 4
```
예상 출력
```
(
```
예제 4
입력
```
4
3 1 2 1 4 3 2 4
```
예상 출력
```
(()()())
```
예제 5
입력
```
4
2 4 3 1 3 4 2 1
```
예상 출력
```
()()()()
```
예제 6
입력
```
4
4 4 3 3 1 2 1 2
```
예상 출력
```
(((())))
```
예제 7
입력
```
4
1 3 1 2 4 4 2 3
```
예상 출력
```
()(())()
```