Il y a $2n$ éléments divisés en $n$ paires.

Pour chaque paire, vous devez assigner soit une parenthèse ouvrante aux deux éléments, soit une parenthèse fermante aux deux éléments. Vous devez faire en sorte que la séquence de parenthèses résultante soit une séquence de parenthèses correcte, ou déterminer qu'il est impossible de le faire. S'il existe plusieurs solutions possibles, trouvez la solution correspondant à la chaîne lexicographiquement la plus petite (parmi $2n$ parenthèses, '(' est plus petit que ')').

Entrée

La première ligne contient un entier $n$ ($1 \le n \le 200\,000$).

La ligne suivante contient $2n$ entiers, $p_1, p_2, \dots, p_{2n}$ ($1 \le p_i \le n$). Tous les entiers de $1$ à $n$ apparaissent exactement deux fois dans cette séquence.

Sortie

S'il est impossible de choisir un type de parenthèse pour chaque paire afin de rendre la séquence de parenthèses dérivée correcte, affichez « ( » (smiley triste russe). Sinon, affichez la séquence de parenthèses correcte lexicographiquement minimale souhaitée.

Exemples

Entrée 1

2
1 2 1 2

Sortie 1

()()

Entrée 2

1
1 1

Sortie 2

(

Entrée 3

4
4 3 1 2 3 2 1 4

Sortie 3

(

Entrée 4

4
3 1 2 1 4 3 2 4

Sortie 4

(()()())

Entrée 5

4
2 4 3 1 3 4 2 1

Sortie 5

()()()()

Entrée 6

4
4 4 3 3 1 2 1 2

Sortie 6

(((())))

Entrée 7

4
1 3 1 2 4 4 2 3

Sortie 7

()(())()