Una permutación de tamaño $n$ es una secuencia de $n$ enteros $a_1,a_2,\ldots,a_n$ en la que cada valor de $1$ a $n$ aparece exactamente una vez.
La secuencia $b_1,b_2,\ldots,b_l$ es una subsecuencia de $a_1,a_2,\ldots,a_n$ si se puede obtener $b$ eliminando algunos elementos de $a$ (es decir, $l\le n$ y existen $i_1<i_2<\ldots<i_l$ tales que $a_{i_t}=b_t$).
- Un elemento $a_i$ de una secuencia se llama récord si es estrictamente mayor que todos los elementos anteriores (es decir, $a_j<a_i$ para todo $1\le j<i$).
- Un elemento $a_i$ de una secuencia se llama antirrécord si es estrictamente menor que todos los elementos anteriores (es decir, $a_j>a_i$ para todo $1\le j<i$).
Se da una permutación $p_1,p_2,\ldots,p_n$ de tamaño $n$. Hay que dividirla en dos subsecuencias no vacías $q$ y $r$. En otras palabras, cada elemento de $p$ debe pertenecer exactamente a una de las subsecuencias. Se debe maximizar la suma del número de récords de $q$ y el número de antirrécords de $r$.
Entrada
Cada prueba consta de varios casos. La primera línea contiene un único entero $t$ ($1\le t\le100\,000$), el número de casos. Las siguientes $2t$ líneas contienen sus descripciones.
La primera línea de la descripción de cada caso contiene un entero $n$, el tamaño de la permutación ($2\le n\le200\,000$).
La segunda línea de la descripción de cada caso contiene $n$ enteros $p_1,p_2,\ldots,p_n$, la permutación original. Se garantiza que cada número de $1$ a $n$ aparece exactamente una vez entre los elementos de $p$.
La suma de $n$ en todos los casos no supera $200\,000$.
Salida
Para cada caso, imprime un entero: la máxima suma posible del número de récords de $q$ y el número de antirrécords de $r$ en una división óptima.
Subtareas
Denotemos por $N$ la suma de los valores de $n$ de todos los casos de una prueba.
| Subtarea | Puntos | Restricciones: $n,N$ | Restricciones adicionales | Subtareas necesarias | Información sobre la evaluación |
|---|---|---|---|---|---|
| $1$ | $21$ | $n\le16$ | $t\le120$ | Ejemplos | Primer error |
| $2$ | $22$ | $n\le200$, $N\le2000$ | Ejemplos, $1$ | Primer error | |
| $3$ | $14$ | $N\le2\,000$ | Ejemplos, $1\text{–}2$ | Primer error | |
| $4$ | $10$ | $N\le10\,000$ | Ejemplos, $1\text{–}3$ | Primer error | |
| $5$ | $13$ | $N\le200\,000$ | La longitud de la subsecuencia decreciente más larga de $p$ no supera $2$ | Primer error | |
| $6$ | $20$ | $N\le200\,000$ | Ejemplos, $1\text{–}5$ | Primer error |
Ejemplos
Entrada 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
Salida 1
5 6 3 5
Nota
Una manera de dividir $p$ de forma óptima en $q$ y $r$ en el primer caso es la siguiente (los récords de $q$ y los antirrécords de $r$ están enmarcados):
- $q=\boxed{1}\ \boxed{2}\ \boxed{3}\ \boxed{5}$
- $r=\boxed{4}$
Una manera de dividir $p$ de forma óptima en $q$ y $r$ en el segundo caso es la siguiente:
- $q=\boxed{3}\ \boxed{8}\ 4\ 1\ 2\ \boxed{9}$
- $r=\boxed{10}\ \boxed{7}\ \boxed{5}\ 6$