Hay $2n$ elementos divididos en $n$ pares.

Para cada par, debes asignar un paréntesis de apertura a ambos elementos, o un paréntesis de cierre a ambos elementos. Debes lograr que la secuencia de paréntesis resultante sea una secuencia de paréntesis correcta o determinar que es imposible. Si existen varias soluciones posibles, encuentra la solución con la cadena lexicográficamente más pequeña (de $2n$ paréntesis, '(' es menor que ')').

Entrada

La primera línea contiene un entero $n$ ($1 \le n \le 200\,000$).

La siguiente línea contiene $2n$ enteros, $p_1, p_2, \dots, p_{2n}$ ($1 \le p_i \le n$). Todos los enteros del $1$ al $n$ aparecen exactamente dos veces en esta secuencia.

Salida

Si es imposible elegir un tipo de paréntesis para cada par de manera que la secuencia de paréntesis derivada sea correcta, imprime ( (carita triste rusa). De lo contrario, imprime la secuencia de paréntesis correcta lexicográficamente mínima deseada.

Ejemplos

Entrada 1

2
1 2 1 2

Salida 1

()()

Entrada 2

1
1 1

Salida 2

(

Entrada 3

4
4 3 1 2 3 2 1 4

Salida 3

(

Entrada 4

4
3 1 2 1 4 3 2 4

Salida 4

(()()())

Entrada 5

4
2 4 3 1 3 4 2 1

Salida 5

()()()()

Entrada 6

4
4 4 3 3 1 2 1 2

Salida 6

(((())))

Entrada 7

4
1 3 1 2 4 4 2 3

Salida 7

()(())()