Þér er gefin runa heiltalna af lengd $n$: $a_1, a_2, \dots, a_n$.

Skoðum allar $n$ mögulegar hringhliðranir (snúninga) á þessari runu. Fyrir upphafsstöðu $p$ ($1 \le p \le n$) er samsvarandi hringhliðrun runan

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

Fyrir þessa hliðruðu runu skilgreinum við forliðahámarksrunu hennar $c_1, c_2, \dots, c_n$ með

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

Við berum saman tvær runur af sömu lengd með venjulegri stafrófsröð (lexicographical order): $c$ er stafrófslega minni en $d$ ef og aðeins ef til er vísir $i$ þannig að $c_1 = d_1, c_2 = d_2, \dots, c_{i-1} = d_{i-1}$ og $c_i < d_i$.

Verkefni þitt er að velja hringhliðrun á upphaflegu rununni þannig að forliðahámarksruna hennar sé stafrófslega minnst meðal allra $n$ mögulegra hringhliðrana.

Inntak

Fyrsta línan inniheldur eina heiltölu $T$ ($1 \le T \le 2 \cdot 10^5$), fjölda prófunartilvika.

Hvert prófunartilvik samanstendur af tveimur línum:

• Fyrsta línan inniheldur eina heiltölu $n$ ($1 \le n \le 5 \cdot 10^5$).
• Önnur línan inniheldur $n$ heiltölur $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $5 \cdot 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur $n$ heiltölur: stafrófslega minnstu forliðahámarksrununa eftir hringhliðrun.

Dæmi

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