„Jeder Anfang muss ein Ende haben“
Für eine Folge $A = (a_1, a_2, \dots, a_m)$ definieren wir:
- die Länge der längsten streng aufsteigenden Teilfolge: $$\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}\}$$
- die Länge der längsten streng absteigenden Teilfolge: $$\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 jede Folge $A$ definieren wir $f(A)$ als die größte ganze Zahl $k$, die folgende Bedingungen erfüllt:
Es existieren $k$ reelle Zahlen $x_1, x_2, \dots, x_k$. Nachdem wir sie der Reihe nach an das Ende von $A$ angehängt haben, erhalten wir eine neue Folge $B = (a_1, a_2, \dots, a_m, x_1, x_2, \dots, x_k)$, für die folgende Bedingungen gelten:
- Alle Elemente der Folge $B$ sind paarweise verschieden;
- $\text{LIS}(B) = \text{LIS}(A)$;
- $\text{LDS}(B) = \text{LDS}(A)$.
Nun ist eine Permutation $P = (P_1, P_2, \dots, P_n)$ der Länge $n$ gegeben. Für jedes Präfix $P^{(i)} = (P_1, P_2, \dots, P_i)$ musst du $f(P^{(i)})$ berechnen und alle Antworten ausgeben.
„Eines Tages werde ich an deine Seite zurückkehren“
Eingabe
Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 10^5$), die die Anzahl der Testfälle angibt.
Für jeden Testfall:
- Die erste Zeile enthält eine ganze Zahl $n$ ($1 \le n \le 2 \cdot 10^5$);
- Die zweite Zeile enthält $n$ ganze Zahlen $P_1, P_2, \dots, P_n$ ($1 \le P_i \le n$), die eine Permutation der Länge $n$ darstellen.
Es wird garantiert, dass die Summe von $n$ über alle Testfälle $2 \cdot 10^5$ nicht überschreitet.
Ausgabe
Gib für jeden Testfall eine Zeile mit $n$ ganzen Zahlen aus, die die Antworten darstellen.
Beispiele
Eingabe 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
Ausgabe 1
0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 2 1 2