Dir ist eine Folge von ganzen Zahlen der Länge $n$ gegeben: $a_1, a_2, \dots, a_n$.

Betrachte alle $n$ möglichen zyklischen Verschiebungen (Rotationen) dieser Folge. Für eine Startposition $p$ ($1 \le p \le n$) ist die entsprechende zyklische Verschiebung die Folge

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

Definiere für diese verschobene Folge ihre Präfixmaximum-Folge $c_1, c_2, \dots, c_n$ durch

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

Wir vergleichen zwei Folgen gleicher Länge mithilfe der üblichen lexikographischen Ordnung: $c$ ist genau dann lexikographisch kleiner als $d$, wenn ein Index $i$ existiert, sodass $c_1 = d_1, c_2 = d_2, \dots, c_{i-1} = d_{i-1}$ und $c_i < d_i$ gilt.

Deine Aufgabe ist es, eine zyklische Verschiebung der ursprünglichen Folge so zu wählen, dass ihre Präfixmaximum-Folge unter allen $n$ möglichen zyklischen Verschiebungen lexikographisch am kleinsten ist.

Eingabe

Die erste Zeile enthält eine einzelne ganze Zahl $T$ ($1 \le T \le 2 \cdot 10^5$), die Anzahl der Testfälle.

Jeder Testfall besteht aus zwei Zeilen:

• Die erste Zeile enthält eine einzelne ganze Zahl $n$ ($1 \le n \le 5 \cdot 10^5$).
• Die zweite Zeile enthält $n$ ganze Zahlen $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

Es wird garantiert, dass die Summe von $n$ über alle Testfälle hinweg $5 \cdot 10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine Zeile mit $n$ ganzen Zahlen aus: die lexikographisch kleinste Präfixmaximum-Folge nach einer zyklischen Verschiebung.

Beispiel

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