Una sequenza di parentesi è una stringa composta dai caratteri ( e ). Una sequenza di parentesi $s_{1,2,\ldots,m}$ è definita valida se soddisfa una delle seguenti condizioni:
- $s$ è vuota.
- $s_1 = $
(, $s_m = $), e $s_{2,3,\ldots,m-1}$ è valida. - Esiste una posizione $k$ ($1 \le k < m$) tale che $s_{1,2,\ldots,k}$ è valida e $s_{k+1,k+2,\ldots,m}$ è valida.
Due posizioni $i, j$ ($1 \le i < j \le m$) nella sequenza di parentesi $s_{1,2,\ldots,m}$ si dicono abbinate se e solo se sia $s_{i,i+1,\ldots,j}$ sia $s_{i+1,i+2,\ldots,j-1}$ sono valide.
Data una sequenza di interi di lunghezza $n$, $a_1, a_2, \ldots, a_n$, dove $n$ è garantito essere pari, costruiamo una nuova sequenza di interi $c_1, c_2, \ldots, c_n$ tramite una sequenza di parentesi valida $b_1, b_2, \ldots, b_n$, tale che $\forall 1 \le i \le n, c_i = a_{p_i}$, dove $p_i$ è la posizione abbinata alla posizione $i$ in $b_{1,2,\ldots,n}$.
Trova una sequenza di parentesi valida $b_{1,2,\ldots,n}$ tale che l'ordine lessicografico di $c_{1,2,\ldots,n}$ sia minimo. Se esistono più soluzioni, stampa una qualsiasi di esse.
Input
La prima riga contiene un intero $T$ ($1 \le T \le 2.5 \times 10^5$), che indica il numero di casi di test.
Per ogni caso di test:
La prima riga contiene un intero $n$ ($1 \le n \le 5 \times 10^5$), che indica la lunghezza della sequenza $a$, ed è garantito che $n$ sia pari.
La seconda riga contiene $n$ interi separati da spazio, che rappresentano $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).
È garantito che la somma di $n$ non superi $5 \times 10^5$.
Output
Per ogni caso di test, stampa una riga contenente una stringa di lunghezza $n$, che rappresenta $b_{1,2,\ldots,n}$.
Esempi
Input 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
Output 1
((())) ()() (()) () ((()))()