”Jokaisella alulla on oltava loppu”
Lukujonolle $A = (a_1, a_2, \dots, a_m)$ määritellään:
- pisimmän aidosti kasvavan alijonon pituus: $$\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}\}$$
- pisimmän aidosti vähenevän alijonon pituus: $$\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}\}$$
Mille tahansa lukujonolle $A$ määritellään $f(A)$ suurimmaksi kokonaisluvuksi $k$, joka täyttää seuraavat ehdot:
On olemassa $k$ reaalilukua $x_1, x_2, \dots, x_k$. Kun ne lisätään järjestyksessä jonon $A$ perään, saadaan uusi lukujono $B = (a_1, a_2, \dots, a_m, x_1, x_2, \dots, x_k)$, jolle pätevät seuraavat ehdot:
- Kaikki lukujonon $B$ alkiot ovat pareittain eri suuria;
- $\text{LIS}(B) = \text{LIS}(A)$;
- $\text{LDS}(B) = \text{LDS}(A)$.
Nyt annetaan pituutta $n$ oleva permutaatio $P = (P_1, P_2, \dots, P_n)$. Jokaiselle etuliitteelle $P^{(i)} = (P_1, P_2, \dots, P_i)$ sinun tulee laskea $f(P^{(i)})$ ja tulostaa kaikki vastaukset.
”Jonakin päivänä palaan rinnallesi”
Syöte
Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^5$), joka ilmoittaa testitapausten määrän.
Jokaiselle testitapaukselle:
- Ensimmäinen rivi sisältää kokonaisluvun $n$ ($1 \le n \le 2 \cdot 10^5$);
- Toinen rivi sisältää $n$ kokonaislukua $P_1, P_2, \dots, P_n$ ($1 \le P_i \le n$), jotka esittävät pituutta $n$ olevan permutaation.
On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $2 \cdot 10^5$.
Tuloste
Tulosta jokaiselle testitapaukselle yksi rivi, joka sisältää $n$ kokonaislukua vastauksina.
Esimerkit
Syöte 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
Tuloste 1
0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 2 1 2