Eine Permutation der Größe $n$ ist eine Folge von $n$ ganzen Zahlen $a_1,a_2,\ldots,a_n$, in der jeder Wert von $1$ bis $n$ genau einmal vorkommt.

Die Folge $b_1,b_2,\ldots,b_l$ ist eine Teilfolge der Folge $a_1,a_2,\ldots,a_n$, wenn sich $b$ durch Löschen einiger Elemente aus $a$ gewinnen lässt (das heißt, $l\le n$ und es gibt $i_1<i_2<\ldots<i_l$, sodass $a_{i_t}=b_t$ gilt).

• Ein Element $a_i$ einer Folge heißt Rekord, wenn es strikt größer als alle vorherigen Elemente ist (also $a_j<a_i$ für alle $1\le j<i$).
• Ein Element $a_i$ einer Folge heißt Antirekord, wenn es strikt kleiner als alle vorherigen Elemente ist (also $a_j>a_i$ für alle $1\le j<i$).

Gegeben ist eine Permutation $p_1,p_2,\ldots,p_n$ der Größe $n$. Sie soll in zwei nichtleere Teilfolgen $q$ und $r$ aufgeteilt werden. Mit anderen Worten muss jedes Element von $p$ in genau eine der Teilfolgen gelangen. Dabei soll die Summe aus der Anzahl der Rekorde in $q$ und der Anzahl der Antirekorde in $r$ maximiert werden.

Eingabe

Jeder Test besteht aus mehreren Testfällen. Die erste Zeile enthält eine einzige ganze Zahl $t$ ($1\le t\le100\,000$), die Anzahl der Testfälle. In den nächsten $2t$ Zeilen folgen die Beschreibungen der Testfälle.

Die erste Zeile jedes Testfalls enthält eine ganze Zahl $n$, die Größe der Permutation ($2\le n\le200\,000$).

Die zweite Zeile jedes Testfalls enthält $n$ ganze Zahlen $p_1,p_2,\ldots,p_n$, die ursprüngliche Permutation. Es ist garantiert, dass unter den Elementen von $p$ jede Zahl von $1$ bis $n$ genau einmal vorkommt.

Die Summe von $n$ über alle Testfälle beträgt höchstens $200\,000$.

Ausgabe

Geben Sie für jeden Testfall eine ganze Zahl aus: die größtmögliche Summe aus der Anzahl der Rekorde in $q$ und der Anzahl der Antirekorde in $r$ bei einer optimalen Aufteilung.

Teilaufgaben

Mit $N$ bezeichnen wir die Summe der Werte von $n$ in allen Testfällen eines Tests.

Beispiele

Eingabe 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

Ausgabe 1

5
6
3
5

Hinweis

Eine Möglichkeit, $p$ im ersten Testfall optimal in $q$ und $r$ aufzuteilen (die Rekorde in $q$ und die Antirekorde in $r$ sind eingerahmt):

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

Eine Möglichkeit, $p$ im zweiten Testfall optimal in $q$ und $r$ aufzuteilen:

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