Dany jest ciąg $2n$ elementów podzielonych na $n$ par.

Dla każdej pary należy przypisać nawias otwierający do obu elementów lub nawias zamykający do obu elementów. Należy sprawdzić, czy możliwe jest utworzenie poprawnego ciągu nawiasowego, a jeśli tak, to należy wyznaczyć taki ciąg. Jeśli istnieje kilka możliwych rozwiązań, należy znaleźć rozwiązanie leksykograficznie najmniejsze (spośród ciągów o długości $2n$, gdzie znak '(' jest mniejszy niż ')').

Wejście

Pierwsza linia zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 200\,000$).

Druga linia zawiera $2n$ liczb całkowitych $p_1, p_2, \dots, p_{2n}$ ($1 \le p_i \le n$). Wszystkie liczby od $1$ do $n$ występują w tym ciągu dokładnie dwa razy.

Wyjście

Jeśli nie jest możliwe dobranie typu nawiasu dla każdej pary tak, aby powstał poprawny ciąg nawiasowy, wypisz ( (rosyjska smutna buźka). W przeciwnym razie wypisz żądany leksykograficznie minimalny poprawny ciąg nawiasowy.

Przykład

Wejście 1

2
1 2 1 2

Wyjście 1

()()

Wejście 2

1
1 1

Wyjście 2

(

Wejście 3

4
4 3 1 2 3 2 1 4

Wyjście 3

(

Wejście 4

4
3 1 2 1 4 3 2 4

Wyjście 4

(()()())

Wejście 5

4
2 4 3 1 3 4 2 1

Wyjście 5

()()()()

Wejście 6

4
4 4 3 3 1 2 1 2

Wyjście 6

(((())))

Wejście 7

4
1 3 1 2 4 4 2 3

Wyjście 7

()(())()