Una secuencia de paréntesis es una cadena compuesta por los caracteres ( y ). Una secuencia de paréntesis $s_{1,2,\ldots,m}$ se define como válida si satisface una de las siguientes condiciones:
- $s$ está vacía.
- $s_1 = $
(, $s_m = $), y $s_{2,3,\ldots,m-1}$ es válida. - Existe una posición $k$ ($1 \le k < m$) tal que $s_{1,2,\ldots,k}$ es válida y $s_{k+1,k+2,\ldots,m}$ es válida.
Se dice que dos posiciones $i, j$ ($1 \le i < j \le m$) en la secuencia de paréntesis $s_{1,2,\ldots,m}$ están emparejadas si y solo si tanto $s_{i,i+1,\ldots,j}$ como $s_{i+1,i+2,\ldots,j-1}$ son válidas.
Dada una secuencia de enteros de longitud $n$, $a_1, a_2, \ldots, a_n$, donde se garantiza que $n$ es par. Construimos una nueva secuencia de enteros $c_1, c_2, \ldots, c_n$ mediante una secuencia de paréntesis válida $b_1, b_2, \ldots, b_n$, tal que $\forall 1 \le i \le n, c_i = a_{p_i}$, donde $p_i$ es la posición emparejada con la posición $i$ en $b_{1,2,\ldots,n}$.
Encuentra una secuencia de paréntesis válida $b_{1,2,\ldots,n}$ tal que el orden lexicográfico de $c_{1,2,\ldots,n}$ sea mínimo. Si hay múltiples soluciones, imprime cualquiera de ellas.
Entrada
La primera línea contiene un entero $T$ ($1 \le T \le 2.5 \times 10^5$), que indica el número de casos de prueba.
Para cada caso de prueba:
La primera línea contiene un entero $n$ ($1 \le n \le 5 \times 10^5$), que indica la longitud de la secuencia $a$, y se garantiza que $n$ es par.
La segunda línea contiene $n$ enteros separados por espacios, que representan $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).
Se garantiza que la suma de $n$ no supera $5 \times 10^5$.
Salida
Para cada caso de prueba, imprime una línea que contenga una cadena de longitud $n$, que represente $b_{1,2,\ldots,n}$.
Ejemplos
Entrada 1
5 6 4 1 5 4 1 1 4 1 2 3 2 4 1 3 1 2 2 2 1 8 8 5 2 6 1 4 3 7
Salida 1
((())) ()() (()) () ((()))()