Une permutation de taille $n$ est une suite de $n$ entiers $a_1, a_2, \ldots, a_n$ dans laquelle chaque valeur de $1$ à $n$ apparaît exactement une fois.

La suite $b_1, b_2, \ldots, b_l$ est une sous-suite de la suite $a_1, a_2, \ldots, a_n$ si l'on peut obtenir $b$ à partir de $a$ en supprimant certains éléments (c'est-à-dire que $l \le n$ et qu'il existe $i_1 < i_2 < \ldots < i_l$ tels que $a_{i_t} = b_t$).

• Un élément $a_i$ de la suite est appelé un record s'il est strictement supérieur à tous les éléments précédents (c'est-à-dire que $a_j < a_i$ pour tout $1 \le j < i$).
• Un élément $a_i$ de la suite est appelé un antirecord s'il est strictement inférieur à tous les éléments précédents (c'est-à-dire que $a_j > a_i$ pour tout $1 \le j < i$).

On vous donne une permutation $p_1, p_2, \ldots, p_n$ de taille $n$. Vous devez la répartir en deux sous-suites non vides $q$ et $r$. Autrement dit, chaque élément de $p$ doit appartenir à exactement une des sous-suites. Il faut maximiser la somme du nombre de records dans $q$ et du nombre d'antirecords dans $r$.

Entrée

Chaque test comprend plusieurs cas de test. La première ligne contient un unique entier $t$ ($1 \le t \le 100\,000$), le nombre de cas de test. Les $2t$ lignes suivantes décrivent les cas de test.

La première ligne de la description de chaque cas de test contient un entier $n$, la taille de la permutation ($2 \le n \le 200\,000$).

La deuxième ligne de la description de chaque cas de test contient $n$ entiers $p_1, p_2, \ldots, p_n$, la permutation initiale. Il est garanti que parmi les éléments de $p$, chaque entier de $1$ à $n$ apparaît exactement une fois.

La somme des valeurs de $n$ sur tous les cas de test ne dépasse pas $200\,000$.

Sortie

Pour chaque cas de test, affichez un entier : la somme maximale possible du nombre de records dans $q$ et du nombre d'antirecords dans $r$ pour une répartition optimale.

Sous-tâches

Notons $N$ la somme des valeurs de $n$ sur tous les cas de test d'un même test.

Exemples

Entrée 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

Sortie 1

5
6
3
5

Remarque

Voici une façon de répartir de manière optimale $p$ en $q$ et $r$ dans le premier cas de test (les records de $q$ et les antirecords de $r$ sont encadrés) :

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

Voici une façon de répartir de manière optimale $p$ en $q$ et $r$ dans le deuxième cas de test :

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