Du får en följd av heltal med längd $n$: $a_1, a_2, \dots, a_n$.

Betrakta alla $n$ möjliga cykliska skift (rotationer) av denna följd. För en startposition $p$ ($1 \le p \le n$) är det motsvarande cykliska skiftet följden

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

För denna skiftade följd definierar vi dess prefixmaximumföljd $c_1, c_2, \dots, c_n$ genom

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

Vi jämför två följder av samma längd med den vanliga lexikografiska ordningen: $c$ är lexikografiskt mindre än $d$ om och endast om det finns ett index $i$ sådant att $c_1 = d_1, c_2 = d_2, \dots, c_{i-1} = d_{i-1}$ och $c_i < d_i$.

Din uppgift är att välja ett cykliskt skift av den ursprungliga följden så att dess prefixmaximumföljd blir lexikografiskt minst bland alla $n$ möjliga cykliska skift.

Indata

Den första raden innehåller ett enda heltal $T$ ($1 \le T \le 2 \cdot 10^5$), antalet testfall.

Varje testfall består av två rader:

• Den första raden innehåller ett enda heltal $n$ ($1 \le n \le 5 \cdot 10^5$).
• Den andra raden innehåller $n$ heltal $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

Det garanteras att summan av $n$ över alla testfall inte överstiger $5 \cdot 10^5$.

Utdata

För varje testfall, skriv ut en rad som innehåller $n$ heltal: den lexikografiskt minsta prefixmaximumföljden efter ett cykliskt skift.

Exempel

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