Permutacją rozmiaru $n$ nazywamy ciąg $n$ liczb całkowitych $a_1,a_2,\ldots,a_n$, w którym każda wartość od $1$ do $n$ występuje dokładnie raz.

Ciąg $b_1,b_2,\ldots,b_l$ jest podciągiem ciągu $a_1,a_2,\ldots,a_n$, jeśli można otrzymać $b$ z $a$, usuwając niektóre elementy (czyli $l\le n$ i istnieją $i_1<i_2<\ldots<i_l$ takie, że $a_{i_t}=b_t$).

• Element ciągu $a_i$ nazywamy rekordem, jeśli jest ściśle większy od wszystkich poprzednich elementów (czyli $a_j<a_i$ dla każdego $1\le j<i$).
• Element ciągu $a_i$ nazywamy antyrekordem, jeśli jest ściśle mniejszy od wszystkich poprzednich elementów (czyli $a_j>a_i$ dla każdego $1\le j<i$).

Dana jest permutacja $p_1,p_2,\ldots,p_n$ rozmiaru $n$. Należy podzielić ją na dwa niepuste podciągi $q$ i $r$. Innymi słowy, każdy element $p$ musi trafić do dokładnie jednego z podciągów. Należy zmaksymalizować sumę liczby rekordów w $q$ i liczby antyrekordów w $r$.

Wejście

Każdy test składa się z kilku zestawów danych. Pierwszy wiersz zawiera jedną liczbę całkowitą $t$ ($1\le t\le 100000$), liczbę zestawów danych. Kolejne $2t$ wierszy zawierają opisy zestawów danych.

Pierwszy wiersz opisu każdego zestawu danych zawiera jedną liczbę całkowitą $n$, rozmiar permutacji ($2\le n\le 200000$).

Drugi wiersz opisu każdego zestawu danych zawiera $n$ liczb całkowitych $p_1,p_2,\ldots,p_n$, początkową permutację. Gwarantuje się, że wśród elementów $p$ każda liczba od $1$ do $n$ występuje dokładnie raz.

Suma $n$ we wszystkich zestawach danych nie przekracza $200000$.

Wyjście

Dla każdego zestawu danych wypisz jedną liczbę całkowitą, największą możliwą sumę liczby rekordów w $q$ i antyrekordów w $r$ przy optymalnym podziale.

Podzadania

Oznaczmy przez $N$ sumę wartości $n$ we wszystkich zestawach danych jednego testu.

Przykład

Wejście 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

Wyjście 1

5
6
3
5

Uwagi

Jeden ze sposobów optymalnego podziału $p$ na $q$ i $r$ w pierwszym zestawie danych (rekordy w $q$ i antyrekordy w $r$ są obramowane):

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

Jeden ze sposobów optymalnego podziału $p$ na $q$ i $r$ w drugim zestawie danych:

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