括弧列とは、文字 ( と ) からなる文字列です。括弧列 $s_{1,2,\ldots,m}$ は、以下の条件のいずれかを満たすとき、正しい(valid である)と定義されます:
- $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}$ における 2 つの位置 $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$ を用いて、$\forall 1 \le i \le n, c_i = a_{p_i}$ となる新しい整数列 $c_1, c_2, \ldots, c_n$ を構築します。ここで $p_i$ は $b_{1,2,\ldots,n}$ において位置 $i$ と対応している位置です。
$c_{1,2,\ldots,n}$ の辞書順が最小となるような正しい括弧列 $b_{1,2,\ldots,n}$ を 1 つ求めてください。解が複数存在する場合は、そのうちのどれを出力しても構いません。
入力
最初の行には、テストケースの数を表す整数 $T$ ($1 \le T \le 2.5 \times 10^5$) が与えられます。
各テストケースについて:
最初の行には、数列 $a$ の長さを表す整数 $n$ ($1 \le n \le 5 \times 10^5$) が与えられます。$n$ は偶数であることが保証されています。
2 行目には、$a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) を表す $n$ 個の空白区切りの整数が与えられます。
すべてのテストケースにおける $n$ の総和は $5 \times 10^5$ を超えないことが保証されています。
出力
各テストケースについて、$b_{1,2,\ldots,n}$ を表す長さ $n$ の文字列を 1 行に出力してください。
入出力例
入力 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
((())) ()() (()) () ((()))()