„Każdy początek musi mieć swój koniec”
Dla ciągu $A = (a_1, a_2, \dots, a_m)$ definiujemy:
- długość najdłuższego ściśle rosnącego podciągu: $$\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}\}$$
- długość najdłuższego ściśle malejącego podciągu: $$\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}\}$$
Dla dowolnego ciągu $A$ definiujemy $f(A)$ jako największą liczbę całkowitą $k$ spełniającą następujące warunki:
Istnieje $k$ liczb rzeczywistych $x_1, x_2, \dots, x_k$. Po dopisaniu ich kolejno na koniec ciągu $A$ otrzymujemy nowy ciąg $B = (a_1, a_2, \dots, a_m, x_1, x_2, \dots, x_k)$, który spełnia następujące warunki:
- Wszystkie elementy w ciągu $B$ są parami różne;
- $\text{LIS}(B) = \text{LIS}(A)$;
- $\text{LDS}(B) = \text{LDS}(A)$.
Teraz dla danej permutacji $P = (P_1, P_2, \dots, P_n)$ o długości $n$, dla każdego prefiksu $P^{(i)} = (P_1, P_2, \dots, P_i)$ musisz obliczyć $f(P^{(i)})$ i wypisać wszystkie odpowiedzi.
„Pewnego dnia wrócę u twego boku”
Wejście
Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 10^5$), oznaczającą liczbę przypadków testowych.
Dla każdego przypadku testowego:
- Pierwszy wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 2 \cdot 10^5$);
- Drugi wiersz zawiera $n$ liczb całkowitych $P_1, P_2, \dots, P_n$ ($1 \le P_i \le n$), reprezentujących permutację o długości $n$.
Gwarantuje się, że suma $n$ po wszystkich przypadkach testowych nie przekracza $2 \cdot 10^5$.
Wyjście
Dla każdego przypadku testowego wypisz jeden wiersz zawierający $n$ liczb całkowitych reprezentujących odpowiedzi.
Przykłady
Wejście 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
Wyjście 1
0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 2 1 2