En parentesfølge er en streng sammensatt av tegnene ( og ). En parentesfølge $s_{1,2,\ldots,m}$ defineres som gyldig hvis den oppfyller ett av følgende vilkår:
- $s$ er tom.
- $s_1 = $
(, $s_m = $), og $s_{2,3,\ldots,m-1}$ er gyldig. - Det finnes en posisjon $k$ ($1 \le k < m$) slik at $s_{1,2,\ldots,k}$ er gyldig og $s_{k+1,k+2,\ldots,m}$ er gyldig.
To posisjoner $i, j$ ($1 \le i < j \le m$) i parentesfølgen $s_{1,2,\ldots,m}$ sies å være matchet hvis og bare hvis både $s_{i,i+1,\ldots,j}$ og $s_{i+1,i+2,\ldots,j-1}$ er gyldige.
Gitt en heltallsfølge med lengde $n$, $a_1, a_2, \ldots, a_n$, der $n$ er garantert å være et partall. Vi konstruerer en ny heltallsfølge $c_1, c_2, \ldots, c_n$ gjennom en gyldig parentesfølge $b_1, b_2, \ldots, b_n$, slik at $\forall 1 \le i \le n, c_i = a_{p_i}$, der $p_i$ er posisjonen som er matchet med posisjon $i$ i $b_{1,2,\ldots,n}$.
Finn en gyldig parentesfølge $b_{1,2,\ldots,n}$ slik at den leksikografiske rekkefølgen til $c_{1,2,\ldots,n}$ minimeres. Hvis det finnes flere løsninger, kan du skrive ut hvilken som helst av dem.
Inndata
Den første linjen inneholder et heltall $T$ ($1 \le T \le 2.5 \times 10^5$), som angir antall testtilfeller.
For hvert testtilfelle:
Den første linjen inneholder et heltall $n$ ($1 \le n \le 5 \times 10^5$), som angir lengden på følgen $a$, og det er garantert at $n$ er et partall.
Den andre linjen inneholder $n$ mellomromseparerte heltall, som representerer $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).
Det er garantert at summen av $n$ ikke overstiger $5 \times 10^5$.
Utdata
For hvert testtilfelle skal du skrive ut en linje som inneholder en streng med lengde $n$, som representerer $b_{1,2,\ldots,n}$.
Eksempler
Inndata 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
Utdata 1
((())) ()() (()) () ((()))()