Til að fagna því að ekkert lið leysti dæmið „Queue Editor“ í undanúrslitum The 3rd Universal Cup hefur Little Cyan Fish fundið upp nýtt dæmi sem snýst um biðröð og... í þetta sinn, hlaða! Hann er með $n$ kúlur merktar frá $1$ til $n$. Kúlunum er í upphafi raðað í biðröð og hann er einnig með tóman hlaða. Á meðan biðröðin er ekki tóm framkvæmir hann eftirfarandi skref:

1. Fjarlægðu kúluna fremst úr biðröðinni. Látum $x$ vera merki hennar.
2. Á meðan hlaðinn er ekki tómur og merki efstu kúlunnar á honum er stærra en $x$, fjarlægðu efstu kúluna af hlaðanum og bættu henni aftast í biðröðina. Kúlunum er bætt við í þeirri röð sem þær eru fjarlægðar.
3. Settu kúluna merkta $x$ efst á hlaðann.

Sýna má fram á að biðröðin verður tóm eftir endanlega mörg skref. Finndu heildarfjölda skipta sem Little Cyan Fish setur kúlu á hlaðann áður en það gerist.

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur eina heiltölu $T$ ($1 \le T$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan eina heiltölu $n$ ($1 \le n \le 5 \times 10^5$), sem gefur til kynna fjölda kúlna. Önnur línan inniheldur $n$ heiltölur $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$), sem gefa til kynna merki kúlnanna í upphaflegu biðröðinni frá fremstu til öftustu. Það er tryggt að $a_1, a_2, \ldots, a_n$ myndi umröðun á $1, 2, \ldots, n$.

Það er tryggt að summa $n$ yfir öll prófunartilvik fari ekki yfir $5 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur eina heiltölu, sem gefur til kynna heildarfjölda skipta sem kúla er sett á hlaðann.

Dæmi

Inntak 1

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

Úttak 1

1
3
5
4

Inntak 2

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

Úttak 2

6
15

Athugasemd

Í fyrra dæminu eru runurnar af merkjum sem sett eru á hlaðann $(1)$, $(1, 2, 3)$, $(2, 1, 3, 2, 3)$ og $(3, 1, 2, 3)$ í prófunartilvikunum fjórum, í sömu röð. Myndin í dæmalýsingunni sýnir þriðja prófunartilvikið í fyrra dæminu.

Í fyrra prófunartilvikinu í seinna dæminu er runan af merkjum sem sett eru á hlaðann $(2, 3, 1, 3, 2, 3)$, þannig að svarið er $6$. Í seinna prófunartilvikinu í seinna dæminu er runan $(1, 3, 4, 6, 2, 5, 6, 4, 3, 6, 5, 4, 6, 5, 6)$, þannig að svarið er $15$.