長さ $n$ の整数列 $a_1, a_2, \dots, a_n$ が与えられます。

この列の可能な $n$ 通りの巡回シフト（回転）をすべて考えます。開始位置 $p$（$1 \le p \le n$）に対して、対応する巡回シフトは次の列です：

$$b_1, b_2, \dots, b_n = a_p, a_{p+1}, \dots, a_n, a_1, a_2, \dots, a_{p-1}.$$

このシフトされた列に対して、その接頭辞最大値列 $c_1, c_2, \dots, c_n$ を次のように定義します：

$$c_i = \max(b_1, b_2, \dots, b_i) \quad \forall i = 1, 2, \dots, n.$$

同じ長さの $2$ つの列を通常の辞書順で比較します。すなわち、ある添字 $i$ が存在して $c_1 = d_1, c_2 = d_2, \dots, c_{i-1} = d_{i-1}$ かつ $c_i < d_i$ となるとき、かつそのときに限り、$c$ は $d$ より辞書順で小さいといいます。

あなたの課題は、可能な $n$ 通りの巡回シフトの中で、その接頭辞最大値列が辞書順で最小となるような元の列の巡回シフトを $1$ つ選ぶことです。

入力

$1$ 行目には、テストケースの個数を表す単一の整数 $T$（$1 \le T \le 2 \cdot 10^5$）が含まれます。

各テストケースは $2$ 行からなります：

• $1$ 行目には単一の整数 $n$（$1 \le n \le 5 \cdot 10^5$）が含まれます。
• $2$ 行目には $n$ 個の整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）が含まれます。

すべてのテストケースにおける $n$ の総和は $5 \cdot 10^5$ を超えないことが保証されています。

出力

各テストケースについて、巡回シフト後の辞書順最小の接頭辞最大値列を表す $n$ 個の整数を含む $1$ 行を出力してください。

入出力例

6
5
5 4 3 2 1
4
1 3 1 3
5
1 2 1 3 1
5
2 3 2 1 1
6
1 2 1 3 1 4
6
2 1 3 1 4 1

1 5 5 5 5
1 3 3 3
1 1 2 2 3
1 1 2 3 3
1 2 2 3 3 4
1 2 2 3 3 4