„Sérhverju upphafi verður að fylgja endir“
Fyrir runu $A = (a_1, a_2, \dots, a_m)$ skilgreinum við:
- lengd lengstu strangt vaxandi hlutrunu: $$\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}\}$$
- lengd lengstu strangt minnkandi hlutrunu: $$\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}\}$$
Fyrir hvaða runu $A$ sem er skilgreinum við $f(A)$ sem stærstu heiltöluna $k$ sem uppfyllir eftirfarandi skilyrði:
Það eru til $k$ rauntölur $x_1, x_2, \dots, x_k$. Eftir að þeim hefur verið bætt í röð aftan við $A$ fáum við nýja runu $B = (a_1, a_2, \dots, a_m, x_1, x_2, \dots, x_k)$, og eftirfarandi skilyrði gilda:
- Öll stök í rununni $B$ eru innbyrðis ólík;
- $\text{LIS}(B) = \text{LIS}(A)$;
- $\text{LDS}(B) = \text{LDS}(A)$.
Nú er gefin umröðun $P = (P_1, P_2, \dots, P_n)$ af lengd $n$. Fyrir hvert forskeyti $P^{(i)} = (P_1, P_2, \dots, P_i)$ þarftu að reikna $f(P^{(i)})$ og prenta út öll svörin.
„Dag einn mun ég snúa aftur þér við hlið“
Inntak
Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 10^5$), sem táknar fjölda prófunartilvika.
Fyrir hvert prófunartilvik:
- Fyrsta línan inniheldur heiltölu $n$ ($1 \le n \le 2 \cdot 10^5$);
- Önnur línan inniheldur $n$ heiltölur $P_1, P_2, \dots, P_n$ ($1 \le P_i \le n$), sem tákna umröðun af lengd $n$.
Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $2 \cdot 10^5$.
Úttak
Fyrir hvert prófunartilvik skal prenta út eina línu sem inniheldur $n$ heiltölur sem tákna svörin.
Dæmi
Inntak 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
Úttak 1
0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 2 1 2