括號序列係由字元 ( 同 ) 組成嘅字串。一個括號序列 $s_{1,2,\ldots,m}$ 如果滿足以下條件之一,就定義為合法:
- $s$ 係空嘅。
- $s_1 = $
(,$s_m = $),而且 $s_{2,3,\ldots,m-1}$ 係合法嘅。 - 存在一個位置 $k$ ($1 \le k < m$),使得 $s_{1,2,\ldots,k}$ 係合法嘅,而且 $s_{k+1,k+2,\ldots,m}$ 係合法嘅。
喺括號序列 $s_{1,2,\ldots,m}$ 入面,兩個位置 $i, j$ ($1 \le i < j \le m$) 被稱為係匹配嘅,當且僅當 $s_{i,i+1,\ldots,j}$ 同 $s_{i+1,i+2,\ldots,j-1}$ 都係合法嘅。
俾定一個長度為 $n$ 嘅整數序列 $a_1, a_2, \ldots, a_n$,其中保證 $n$ 係偶數。我哋透過一個合法嘅括號序列 $b_1, b_2, \ldots, b_n$ 嚟構造一個新嘅整數序列 $c_1, c_2, \ldots, c_n$,使得 $\forall 1 \le i \le n, c_i = a_{p_i}$,其中 $p_i$ 係喺 $b_{1,2,\ldots,n}$ 入面同位置 $i$ 匹配嘅位置。
請搵出一個合法嘅括號序列 $b_{1,2,\ldots,n}$,使得 $c_{1,2,\ldots,n}$ 嘅字典序最細。如果有多個解,輸出其中任意一個即可。
輸入格式
第一行包含一個整數 $T$ ($1 \le T \le 2.5 \times 10^5$),表示測試數據嘅組數。
對於每組測試數據:
第一行包含一個整數 $n$ ($1 \le n \le 5 \times 10^5$),表示序列 $a$ 嘅長度,而且保證 $n$ 係偶數。
第二行包含 $n$ 個以空格分隔嘅整數,代表 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$)。
保證所有測試數據入面 $n$ 嘅總和唔超過 $5 \times 10^5$。
輸出格式
對於每組測試數據,輸出一行包含一個長度為 $n$ 嘅字串,代表 $b_{1,2,\ldots,n}$。
範例
輸入格式 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
輸出格式 1
((())) ()() (()) () ((()))()