Une séquence de parenthèses est une chaîne composée des caractères ( et ). Une séquence de parenthèses $s_{1,2,\ldots,m}$ est dite valide si elle vérifie l'une des conditions suivantes :
- $s$ est vide.
- $s_1 = $
(, $s_m = $), et $s_{2,3,\ldots,m-1}$ est valide. - Il existe une position $k$ ($1 \le k < m$) telle que $s_{1,2,\ldots,k}$ est valide et $s_{k+1,k+2,\ldots,m}$ est valide.
Deux positions $i, j$ ($1 \le i < j \le m$) dans la séquence de parenthèses $s_{1,2,\ldots,m}$ sont dites appariées si et seulement si $s_{i,i+1,\ldots,j}$ et $s_{i+1,i+2,\ldots,j-1}$ sont toutes deux valides.
On vous donne une suite d'entiers de longueur $n$, $a_1, a_2, \ldots, a_n$, où $n$ est garanti pair. Nous construisons une nouvelle suite d'entiers $c_1, c_2, \ldots, c_n$ à l'aide d'une séquence de parenthèses valide $b_1, b_2, \ldots, b_n$, telle que $\forall 1 \le i \le n, c_i = a_{p_i}$, où $p_i$ est la position appariée avec la position $i$ dans $b_{1,2,\ldots,n}$.
Trouvez une séquence de parenthèses valide $b_{1,2,\ldots,n}$ telle que l'ordre lexicographique de $c_{1,2,\ldots,n}$ soit minimisé. S'il existe plusieurs solutions, affichez l'une quelconque d'entre elles.
Entrée
La première ligne contient un entier $T$ ($1 \le T \le 2.5 \times 10^5$), indiquant le nombre de cas de test.
Pour chaque cas de test :
La première ligne contient un entier $n$ ($1 \le n \le 5 \times 10^5$), indiquant la longueur de la suite $a$, et il est garanti que $n$ est pair.
La deuxième ligne contient $n$ entiers séparés par des espaces, représentant $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).
Il est garanti que la somme des $n$ ne dépasse pas $5 \times 10^5$.
Sortie
Pour chaque cas de test, affichez une ligne contenant une chaîne de longueur $n$, représentant $b_{1,2,\ldots,n}$.
Exemples
Entrée 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
Sortie 1
((())) ()() (()) () ((()))()