$2n$개의 원소가 $n$개의 쌍으로 나누어져 있습니다.

각 쌍에 대해, 두 원소 모두에 여는 괄호를 할당하거나, 두 원소 모두에 닫는 괄호를 할당해야 합니다. 결과로 만들어지는 괄호 수열이 올바른 괄호 수열이 되도록 만들어야 하며, 만약 불가능하다면 불가능함을 판별해야 합니다. 가능한 해결책이 여러 개 있다면, 사전순으로 가장 작은 문자열(괄호 $2n$개로 구성되며, '('가 ')'보다 작음)을 찾으십시오.

입력

첫 번째 줄에는 정수 $n$ ($1 \le n \le 200\,000$)이 주어집니다.

다음 줄에는 $2n$개의 정수 $p_1, p_2, \dots, p_{2n}$ ($1 \le p_i \le n$)이 주어집니다. $1$부터 $n$까지의 모든 정수는 이 수열에 정확히 두 번씩 나타납니다.

출력

각 쌍에 대해 괄호 유형을 선택하여 올바른 괄호 수열을 만드는 것이 불가능하다면, ( (러시아식 슬픈 이모티콘)을 출력하십시오. 가능하다면, 사전순으로 가장 작은 올바른 괄호 수열을 출력하십시오.

예제

입력 1

2
1 2 1 2

출력 1

()()

입력 2

1
1 1

출력 2

(

입력 3

4
4 3 1 2 3 2 1 4

출력 3

(

입력 4

4
3 1 2 1 4 3 2 4

출력 4

(()()())

입력 5

4
2 4 3 1 3 4 2 1

출력 5

()()()()

입력 6

4
4 4 3 3 1 2 1 2

출력 6

(((())))

입력 7

4
1 3 1 2 4 4 2 3

출력 7

()(())()