« Tout commencement doit avoir une fin »
Pour une suite $A = (a_1, a_2, \dots, a_m)$, on définit :
- la longueur de la plus longue sous-suite strictement croissante : $$\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 longueur de la plus longue sous-suite strictement décroissante : $$\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}\}$$
Pour toute suite $A$, on définit $f(A)$ comme le plus grand entier $k$ vérifiant les conditions suivantes :
Il existe $k$ nombres réels $x_1, x_2, \dots, x_k$. Après les avoir ajoutés dans l'ordre à la fin de $A$, on obtient une nouvelle suite $B = (a_1, a_2, \dots, a_m, x_1, x_2, \dots, x_k)$, et les conditions suivantes sont vérifiées :
- Tous les éléments de la suite $B$ sont deux à deux distincts ;
- $\text{LIS}(B) = \text{LIS}(A)$;
- $\text{LDS}(B) = \text{LDS}(A)$.
Étant donné une permutation $P = (P_1, P_2, \dots, P_n)$ de longueur $n$, pour chaque préfixe $P^{(i)} = (P_1, P_2, \dots, P_i)$, vous devez calculer $f(P^{(i)})$ et afficher toutes les réponses.
« Un jour, je reviendrai à tes côtés »
Entrée
La première ligne contient un entier $T$ ($1 \le T \le 10^5$), indiquant le nombre de cas de test.
Pour chaque cas de test :
- La première ligne contient un entier $n$ ($1 \le n \le 2 \cdot 10^5$) ;
- La deuxième ligne contient $n$ entiers $P_1, P_2, \dots, P_n$ ($1 \le P_i \le n$), représentant une permutation de longueur $n$.
Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $2 \cdot 10^5$.
Sortie
Pour chaque cas de test, affichez une ligne contenant $n$ entiers représentant les réponses.
Exemples
Entrée 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
Sortie 1
0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 2 1 2