On vous donne une suite d'entiers de longueur $n$ : $a_1, a_2, \dots, a_n$.

Considérez les $n$ décalages circulaires (rotations) possibles de cette suite. Pour une position de départ $p$ ($1 \le p \le n$), le décalage circulaire correspondant est la suite

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

Pour cette suite décalée, on définit sa suite des maximums de préfixes $c_1, c_2, \dots, c_n$ par

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

Nous comparons deux suites de même longueur à l'aide de l'ordre lexicographique usuel : $c$ est lexicographiquement plus petite que $d$ si et seulement s'il existe un indice $i$ tel que $c_1 = d_1, c_2 = d_2, \dots, c_{i-1} = d_{i-1}$ et $c_i < d_i$.

Votre tâche consiste à choisir un décalage circulaire de la suite initiale tel que sa suite des maximums de préfixes soit la plus petite possible dans l'ordre lexicographique parmi les $n$ décalages circulaires possibles.

Entrée

La première ligne contient un seul entier $T$ ($1 \le T \le 2 \cdot 10^5$), le nombre de cas de test.

Chaque cas de test se compose de deux lignes :

• La première ligne contient un seul entier $n$ ($1 \le n \le 5 \cdot 10^5$).
• La deuxième ligne contient $n$ entiers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

Il est garanti que la somme de $n$ sur l'ensemble des cas de test ne dépasse pas $5 \cdot 10^5$.

Sortie

Pour chaque cas de test, affichez une ligne contenant $n$ entiers : la suite des maximums de préfixes lexicographiquement minimale après décalage circulaire.

Exemple

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