En permutation av storlek $n$ är en följd av $n$ heltal $a_1,a_2,\ldots,a_n$, där varje värde från $1$ till $n$ förekommer exakt en gång.

Följden $b_1,b_2,\ldots,b_l$ är en delföljd av följden $a_1,a_2,\ldots,a_n$ om $b$ kan erhållas från $a$ genom att ta bort vissa element (det vill säga $l\le n$ och det finns $i_1<i_2<\ldots<i_l$ sådana att $a_{i_t}=b_t$).

• Ett element $a_i$ i följden kallas ett rekord om det är strikt större än alla föregående element (det vill säga $a_j<a_i$ för alla $1\le j<i$).
• Ett element $a_i$ i följden kallas ett antirekord om det är strikt mindre än alla föregående element (det vill säga $a_j>a_i$ för alla $1\le j<i$).

Du får en permutation $p_1,p_2,\ldots,p_n$ av storlek $n$. Dela upp den i två icke-tomma delföljder $q$ och $r$. Med andra ord måste varje element i $p$ hamna i exakt en av delföljderna. Summan av antalet rekord i $q$ och antalet antirekord i $r$ ska maximeras.

Indata

Varje test består av flera testfall. Den första raden innehåller ett enda heltal $t$ ($1\le t\le 100\,000$), antalet testfall. De följande $2t$ raderna beskriver testfallen.

Den första raden i beskrivningen av varje testfall innehåller ett heltal $n$, permutationens storlek ($2\le n\le 200\,000$).

Den andra raden i beskrivningen av varje testfall innehåller $n$ heltal $p_1,p_2,\ldots,p_n$, den ursprungliga permutationen. Det garanteras att varje tal från $1$ till $n$ förekommer exakt en gång bland elementen i $p$.

Summan av $n$ över alla testfall överstiger inte $200\,000$.

Utdata

Skriv för varje testfall ut ett heltal: den största möjliga summan av antalet rekord i $q$ och antalet antirekord i $r$ vid en optimal uppdelning.

Deluppgifter

Låt $N$ beteckna summan av värdena $n$ för alla testfall i ett test.

Exempel

Indata 1

4
5
4 1 2 3 5
10
3 8 10 4 1 2 7 9 5 6
3
1 2 3
6
4 2 5 1 6 3

Utdata 1

5
6
3
5

Förklaring

Ett sätt att optimalt dela upp $p$ i $q$ och $r$ i det första testfallet (rekorden i $q$ och antirekorden i $r$ är inramade):

• $q=\boxed{1}\ \boxed{2}\ \boxed{3}\ \boxed{5}$
• $r=\boxed{4}$

Ett sätt att optimalt dela upp $p$ i $q$ och $r$ i det andra testfallet:

• $q=\boxed{3}\ \boxed{8}\ 4\ 1\ 2\ \boxed{9}$
• $r=\boxed{10}\ \boxed{7}\ \boxed{5}\ 6$