”Varje början måste ha ett slut”
För en talföljd $A = (a_1, a_2, \dots, a_m)$ definierar vi:
- längden på den längsta strikt växande delföljden: $$\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}\}$$
- längden på den längsta strikt avtagande delföljden: $$\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}\}$$
För varje talföljd $A$ definierar vi $f(A)$ som det största heltalet $k$ som uppfyller följande villkor:
Det finns $k$ reella tal $x_1, x_2, \dots, x_k$. Efter att vi har lagt till dem i ordning i slutet av $A$ får vi en ny talföljd $B = (a_1, a_2, \dots, a_m, x_1, x_2, \dots, x_k)$, och följande villkor gäller:
- Alla element i talföljden $B$ är parvis olika;
- $\text{LIS}(B) = \text{LIS}(A)$;
- $\text{LDS}(B) = \text{LDS}(A)$.
Nu ges en permutation $P = (P_1, P_2, \dots, P_n)$ av längd $n$. För varje prefix $P^{(i)} = (P_1, P_2, \dots, P_i)$ ska du beräkna $f(P^{(i)})$ och skriva ut alla svar.
”En dag kommer jag att återvända till din sida”
Indata
Den första raden innehåller ett heltal $T$ ($1 \le T \le 10^5$), som anger antalet testfall.
För varje testfall:
- Den första raden innehåller ett heltal $n$ ($1 \le n \le 2 \cdot 10^5$);
- Den andra raden innehåller $n$ heltal $P_1, P_2, \dots, P_n$ ($1 \le P_i \le n$), som representerar en permutation av längd $n$.
Det garanteras att summan av $n$ över alla testfall inte överstiger $2 \cdot 10^5$.
Utdata
För varje testfall, skriv ut en rad som innehåller $n$ heltal som representerar svaren.
Exempel
Indata 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