Eine Klammerfolge ist eine Zeichenkette, die aus den Zeichen ( und ) besteht. Eine Klammerfolge $s_{1,2,\ldots,m}$ ist als gültig definiert, wenn sie eine der folgenden Bedingungen erfüllt:
- $s$ ist leer.
- $s_1 = $
(, $s_m = $), und $s_{2,3,\ldots,m-1}$ ist gültig. - Es gibt eine Position $k$ ($1 \le k < m$), sodass $s_{1,2,\ldots,k}$ gültig ist und $s_{k+1,k+2,\ldots,m}$ gültig ist.
Zwei Positionen $i, j$ ($1 \le i < j \le m$) in der Klammerfolge $s_{1,2,\ldots,m}$ heißen genau dann einander zugeordnet, wenn sowohl $s_{i,i+1,\ldots,j}$ als auch $s_{i+1,i+2,\ldots,j-1}$ gültig sind.
Gegeben ist eine ganzzahlige Folge der Länge $n$, $a_1, a_2, \ldots, a_n$, wobei $n$ garantiert gerade ist. Wir konstruieren eine neue ganzzahlige Folge $c_1, c_2, \ldots, c_n$ mithilfe einer gültigen Klammerfolge $b_1, b_2, \ldots, b_n$, sodass $\forall 1 \le i \le n, c_i = a_{p_i}$ gilt, wobei $p_i$ die der Position $i$ in $b_{1,2,\ldots,n}$ zugeordnete Position ist.
Finde eine gültige Klammerfolge $b_{1,2,\ldots,n}$, sodass die lexikographische Ordnung von $c_{1,2,\ldots,n}$ minimiert wird. Falls es mehrere Lösungen gibt, gib eine beliebige davon aus.
Eingabe
Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 2.5 \times 10^5$), die die Anzahl der Testfälle angibt.
Für jeden Testfall:
Die erste Zeile enthält eine ganze Zahl $n$ ($1 \le n \le 5 \times 10^5$), die die Länge der Folge $a$ angibt, wobei garantiert ist, dass $n$ gerade ist.
Die zweite Zeile enthält $n$ durch Leerzeichen getrennte ganze Zahlen, die $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) darstellen.
Es wird garantiert, dass die Summe von $n$ den Wert $5 \times 10^5$ nicht überschreitet.
Ausgabe
Gib für jeden Testfall eine Zeile mit einer Zeichenkette der Länge $n$ aus, die $b_{1,2,\ldots,n}$ darstellt.
Beispiele
Eingabe 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
Ausgabe 1
((())) ()() (()) () ((()))()