«Ogni inizio deve avere una fine»
Per una sequenza $A = (a_1, a_2, \dots, a_m)$, definiamo:
- la lunghezza della più lunga sottosequenza strettamente crescente: $$\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 lunghezza della più lunga sottosequenza strettamente decrescente: $$\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}\}$$
Per qualsiasi sequenza $A$, definiamo $f(A)$ come il massimo intero $k$ che soddisfa le seguenti condizioni:
Esistono $k$ numeri reali $x_1, x_2, \dots, x_k$. Dopo averli aggiunti in ordine alla fine di $A$, otteniamo una nuova sequenza $B = (a_1, a_2, \dots, a_m, x_1, x_2, \dots, x_k)$, e valgono le seguenti condizioni:
- Tutti gli elementi nella sequenza $B$ sono a due a due distinti;
- $\text{LIS}(B) = \text{LIS}(A)$;
- $\text{LDS}(B) = \text{LDS}(A)$.
Ora, data una permutazione $P = (P_1, P_2, \dots, P_n)$ di lunghezza $n$, per ciascun prefisso $P^{(i)} = (P_1, P_2, \dots, P_i)$, devi calcolare $f(P^{(i)})$ e stampare tutte le risposte.
«Un giorno tornerò al tuo fianco»
Input
La prima riga contiene un intero $T$ ($1 \le T \le 10^5$), che indica il numero di casi di test.
Per ciascun caso di test:
- La prima riga contiene un intero $n$ ($1 \le n \le 2 \cdot 10^5$);
- La seconda riga contiene $n$ interi $P_1, P_2, \dots, P_n$ ($1 \le P_i \le n$), che rappresentano una permutazione di lunghezza $n$.
È garantito che la somma di $n$ su tutti i casi di test non supera $2 \cdot 10^5$.
Output
Per ciascun caso di test, stampa una riga contenente $n$ interi che rappresentano le risposte.
Esempi
Input 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
Output 1
0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 2 1 2