«Todo comienzo debe tener un final»
Para una sucesión $A = (a_1, a_2, \dots, a_m)$, definimos:
- la longitud de la subsucesión estrictamente creciente más larga: $$\text{LIS}(A) = \max\{k \mid \exists 1 \le i_1 < i_2 < \dots < i_k \le m, a_{i_1} < a_{i_2} < \dots < a_{i_k}\}$$
- la longitud de la subsucesión estrictamente decreciente más larga: $$\text{LDS}(A) = \max\{k \mid \exists 1 \le i_1 < i_2 < \dots < i_k \le m, a_{i_1} > a_{i_2} > \dots > a_{i_k}\}$$
Para cualquier sucesión $A$, definimos $f(A)$ como el mayor entero $k$ que satisface las siguientes condiciones:
Existen $k$ números reales $x_1, x_2, \dots, x_k$. Tras añadirlos en orden al final de $A$, obtenemos una nueva sucesión $B = (a_1, a_2, \dots, a_m, x_1, x_2, \dots, x_k)$, y se cumplen las siguientes condiciones:
- Todos los elementos de la sucesión $B$ son distintos dos a dos;
- $\text{LIS}(B) = \text{LIS}(A)$;
- $\text{LDS}(B) = \text{LDS}(A)$.
Ahora, dada una permutación $P = (P_1, P_2, \dots, P_n)$ de longitud $n$, para cada prefijo $P^{(i)} = (P_1, P_2, \dots, P_i)$, debes calcular $f(P^{(i)})$ e imprimir todas las respuestas.
«Algún día volveré a tu lado»
Entrada
La primera línea contiene un entero $T$ ($1 \le T \le 10^5$), que indica el número de casos de prueba.
Para cada caso de prueba:
- La primera línea contiene un entero $n$ ($1 \le n \le 2 \cdot 10^5$);
- La segunda línea contiene $n$ enteros $P_1, P_2, \dots, P_n$ ($1 \le P_i \le n$), que representan una permutación de longitud $n$.
Se garantiza que la suma de $n$ en todos los casos de prueba no supera $2 \cdot 10^5$.
Salida
Para cada caso de prueba, imprime una línea con $n$ enteros que representen las respuestas.
Ejemplos
Entrada 1
5 2 1 2 3 1 3 2 4 3 4 1 2 5 2 5 1 3 4 6 3 6 2 1 4 5
Salida 1
0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 2 1 2