Một dãy ngoặc là một xâu được tạo bởi các ký tự ( và ). Một dãy ngoặc $s_{1,2,\ldots,m}$ được định nghĩa là hợp lệ nếu nó thỏa mãn một trong các điều kiện sau:
- $s$ rỗng.
- $s_1 = $
(, $s_m = $), và $s_{2,3,\ldots,m-1}$ là hợp lệ. - Tồn tại một vị trí $k$ ($1 \le k < m$) sao cho $s_{1,2,\ldots,k}$ hợp lệ và $s_{k+1,k+2,\ldots,m}$ hợp lệ.
Hai vị trí $i, j$ ($1 \le i < j \le m$) trong dãy ngoặc $s_{1,2,\ldots,m}$ được gọi là khớp với nhau khi và chỉ khi cả $s_{i,i+1,\ldots,j}$ lẫn $s_{i+1,i+2,\ldots,j-1}$ đều hợp lệ.
Cho một dãy số nguyên có độ dài $n$, $a_1, a_2, \ldots, a_n$, trong đó $n$ được đảm bảo là số chẵn. Ta xây dựng một dãy số nguyên mới $c_1, c_2, \ldots, c_n$ thông qua một dãy ngoặc hợp lệ $b_1, b_2, \ldots, b_n$, sao cho $\forall 1 \le i \le n, c_i = a_{p_i}$, trong đó $p_i$ là vị trí khớp với vị trí $i$ trong $b_{1,2,\ldots,n}$.
Hãy tìm một dãy ngoặc hợp lệ $b_{1,2,\ldots,n}$ sao cho thứ tự từ điển của $c_{1,2,\ldots,n}$ là nhỏ nhất. Nếu có nhiều phương án, hãy in ra một phương án bất kỳ.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 2.5 \times 10^5$), cho biết số lượng bộ dữ liệu.
Với mỗi bộ dữ liệu:
Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 5 \times 10^5$), cho biết độ dài của dãy $a$, và đảm bảo rằng $n$ là số chẵn.
Dòng thứ hai chứa $n$ số nguyên cách nhau bởi dấu cách, biểu thị $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).
Đảm bảo rằng tổng của $n$ không vượt quá $5 \times 10^5$.
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một dòng chứa một xâu có độ dài $n$, biểu thị $b_{1,2,\ldots,n}$.
Ví dụ
Dữ liệu vào 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
Dữ liệu ra 1
((())) ()() (()) () ((()))()