括號序列是由字元 ( 與 ) 所組成的字串。一個括號序列 $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
((())) ()() (()) () ((()))()