secvente

Considerăm şirul de numere naturale nenule distincte $a_1, a_2, \dots, a_N$. Notăm cu $L_i$ lungimea maximă a unei secvențe de elemente cu valori consecutive care se poate obţine prin ordonarea crescătoare a primelor $i$ elemente din şirul dat. De exemplu, pentru șirul $7, 2, 3, 8, 20, 4, 10, 9$ avem:
$L_1 = 1$, $L_2 = 1$, $L_3 = 2$, $L_4 = 2$, $L_5 = 2$, $L_6 = 3$, $L_7 = 3$, $L_8 = 4$.

Cerință

Să se determine $L_1, L_2, \ldots, L_N$.

Date de intrare

Fişierul secvente.in conţine pe prima linie numărul natural $N$. Pe fiecare din următoarele $N$ linii se găseşte câte un număr natural, deci pe linia $i+1$ se va afla elementul $a_i$, pentru $i = 1,2, \dots N$.

Date de ieșire

Fişierul secvente.out conţine exact $N$ linii. Pe linia $i = 1,2, \dots N$ se va afișa valoarea $L_i$.

Restricții și precizări

• $3 \leq N \leq 200 \ 000$
• $1 \leq a_i \leq 1 \ 000 \ 000$, pentru orice $i = 1,2, \dots N$
• Pentru $35\%$ din teste se garantează că $N \leq 1 \ 000$

Exemplu

secvente.in

8
7
3
2
8
20
4
10
9

secvente.out

1
1
2
2
2
3
3
4

Explicație

• $L_1$: Șirul este $7$. Lungimea maximă este $1$.
• $L_2$: Șirul este $7, 3$. Lungimea maximă este $1$.
• $L_3$: Șirul este $7, 3, 2$. Şirul sortat este $\textcolor{red}{2, 3}, 7$. Lungimea maximă este $2$ (dată de secvenţa $2, 3$).
• $L_4$: Șirul este $7, 3, 2, 8$. Lungimea maximă este $2$ (dată de secvența $2, 3$).
• $L_5$: Șirul este $7, 3, 2, 8, 20$. Lungimea maximă este $2$ (dată de secvența $2, 3$).
• $L_6$: Șirul este $7, 3, 2, 8, 20, 4$. Şirul sortat este $\textcolor{red}{2, 3, 4}, 7, 8, 20$. Lungimea maximă este $3$ (dată de secvenţa $2, 3, 4$).
• $L_7$: Șirul este $7, 3, 2, 8, 20, 4, 10$. Lungimea maximă este $3$ (dată de secvența $2, 3, 4$).
• $L_8$: Șirul este $7, 3, 2, 8, 20, 4, 10, 9$. Şirul sortat este $2, 3, 4, \textcolor{red}{7, 8, 9, 10}, 20$. Lungimea maximă este $4$ (dată de secvenţa $7, 8, 9, 10$).