Brackets

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

요약

각 값이 나타나는 두 위치를 모두 여는 괄호 또는 모두 닫는 괄호로 정해 올바른 괄호 문자열을 만듭니다. 사전순으로 가장 작은 문자열을 출력하고, 불가능하면 슬픈 이모티콘을 출력합니다.

난이도: 보통10점 중 7점
유형: 그리디, 세그먼트 트리, 문자열
정답자: 아직 제출이 없습니다

문제

$2n$ 개의 원소가 $n$ 개의 쌍으로 나뉘어 있다.

각 쌍마다 두 원소 모두에 여는 괄호를 붙이거나, 두 원소 모두에 닫는 괄호를 붙여야 한다. 이렇게 만든 괄호열은 올바른 괄호열이어야 하며, 그럴 수 없다면 그 사실을 알려야 한다. 가능한 방법이 여럿이면 '('가 ')'보다 작다고 할 때 사전순으로 가장 앞서는 괄호열을 구한다.

입력

첫 줄에 정수 $n$ ( $1 \leq n \leq 200\,000$ )이 주어진다.

다음 줄에는 정수 $p_1, p_2, \ldots, p_{2n}$ ( $1 \leq p_i \leq n$ )이 주어진다. $1$ 부터 $n$ 까지의 정수는 각각 이 수열에 정확히 두 번씩 나타난다.

출력

올바른 괄호열을 만들 수 없으면 러시아식 슬픈 얼굴 이모티콘인 '('를 출력한다. 그렇지 않으면 길이가 $2n$ 인 올바른 괄호열 중 사전순으로 가장 작은 것을 출력한다.

예제5

예제 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
```
예상 출력
```
()()()()
```