Sebuah barisan tanda kurung adalah string yang tersusun atas karakter ( dan ). Sebuah barisan tanda kurung $s_{1,2,\ldots,m}$ didefinisikan valid jika memenuhi salah satu dari kondisi berikut:
- $s$ kosong.
- $s_1 = $
(, $s_m = $), dan $s_{2,3,\ldots,m-1}$ valid. - Terdapat suatu posisi $k$ ($1 \le k < m$) sedemikian sehingga $s_{1,2,\ldots,k}$ valid, dan $s_{k+1,k+2,\ldots,m}$ valid.
Dua posisi $i, j$ ($1 \le i < j \le m$) pada barisan tanda kurung $s_{1,2,\ldots,m}$ dikatakan berpasangan jika dan hanya jika baik $s_{i,i+1,\ldots,j}$ maupun $s_{i+1,i+2,\ldots,j-1}$ keduanya valid.
Diberikan sebuah barisan bilangan bulat dengan panjang $n$, yaitu $a_1, a_2, \ldots, a_n$, di mana $n$ dijamin genap. Kita membentuk sebuah barisan bilangan bulat baru $c_1, c_2, \ldots, c_n$ melalui sebuah barisan tanda kurung valid $b_1, b_2, \ldots, b_n$, sedemikian sehingga $\forall 1 \le i \le n, c_i = a_{p_i}$, di mana $p_i$ adalah posisi yang berpasangan dengan posisi $i$ pada $b_{1,2,\ldots,n}$.
Carilah sebuah barisan tanda kurung valid $b_{1,2,\ldots,n}$ sedemikian sehingga urutan leksikografis dari $c_{1,2,\ldots,n}$ menjadi sekecil mungkin. Jika terdapat beberapa solusi, keluarkan salah satu saja di antaranya.
Masukan
Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 2.5 \times 10^5$), yang menyatakan banyaknya kasus uji.
Untuk setiap kasus uji:
Baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 5 \times 10^5$), yang menyatakan panjang barisan $a$, dan dijamin bahwa $n$ genap.
Baris kedua berisi $n$ bilangan bulat yang dipisahkan spasi, yang menyatakan $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).
Dijamin bahwa jumlah dari $n$ tidak melebihi $5 \times 10^5$.
Keluaran
Untuk setiap kasus uji, keluarkan satu baris berisi sebuah string dengan panjang $n$, yang menyatakan $b_{1,2,\ldots,n}$.
Contoh
Masukan 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
Keluaran 1
((())) ()() (()) () ((()))()