«Enhver begynnelse må ha en slutt»
For en følge $A = (a_1, a_2, \dots, a_m)$ definerer vi:
- lengden på den lengste strengt stigende delfølgen: $$\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}\}$$
- lengden på den lengste strengt synkende delfølgen: $$\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}\}$$
For enhver følge $A$ definerer vi $f(A)$ som det største heltallet $k$ som oppfyller følgende betingelser:
Det finnes $k$ reelle tall $x_1, x_2, \dots, x_k$. Etter at vi har lagt dem til i rekkefølge på slutten av $A$, får vi en ny følge $B = (a_1, a_2, \dots, a_m, x_1, x_2, \dots, x_k)$, og følgende betingelser gjelder:
- Alle elementene i følgen $B$ er parvis forskjellige;
- $\text{LIS}(B) = \text{LIS}(A)$;
- $\text{LDS}(B) = \text{LDS}(A)$.
Nå er det gitt en permutasjon $P = (P_1, P_2, \dots, P_n)$ av lengde $n$. For hvert prefiks $P^{(i)} = (P_1, P_2, \dots, P_i)$ må du beregne $f(P^{(i)})$ og skrive ut alle svarene.
«En dag vil jeg vende tilbake til din side»
Inndata
Den første linjen inneholder et heltall $T$ ($1 \le T \le 10^5$), som angir antall testtilfeller.
For hvert testtilfelle:
- Den første linjen inneholder et heltall $n$ ($1 \le n \le 2 \cdot 10^5$);
- Den andre linjen inneholder $n$ heltall $P_1, P_2, \dots, P_n$ ($1 \le P_i \le n$), som representerer en permutasjon av lengde $n$.
Det garanteres at summen av $n$ over alle testtilfeller ikke overstiger $2 \cdot 10^5$.
Utdata
For hvert testtilfelle skal du skrive ut én linje som inneholder $n$ heltall som representerer svarene.
Eksempler
Inndata 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
Utdata 1
0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 2 1 2