Rezolvare PBinfo #1639

Considerăm şirul de numere naturale nenule distincte \(a_1, a_2, …, 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ța

Să se determine \(L_1, L_2, …, 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...N.

Date de ieșire

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

Restricții și precizări

• 3 ≤ N ≤ 200.000
• 1 ≤ \(a_i\) ≤ 1.000.000, pentru orice i = 1...N
• Pentru 35% din teste se garantează că N ≤ 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: 7. Lungime maximă 1.
\(L_2\). Șirul: 7, 3. Lungime maximă 1.
\(L_1\). Șirul: 7, 3, 2. Şirul sortat este 2, 3, 7. Lungimea maximă este 2 (dată de secvenţa 2, 3).
\(L_4\). Șirul: 7, 3, 2, 8. Lungime maximă 2 (dată de 2, 3)
\(L_5\). Șirul: 7, 3, 2, 8, 20. Lungime maximă 2 (dată de 2, 3).
\(L_6\). Șirul: 7, 3, 2, 8, 20, 4. Şirul sortat este 2, 3, 4, 7, 8, 20. Lungimea maximă este 3 (dată de secvenţa 2, 3, 4).
\(L_7\). Șirul: 7, 3, 2, 8, 20, 4, 10. Lungime maximă 3 (dată de 2, 3, 4).
\(L_8\). Șirul: 7, 3, 2, 8, 20, 4, 10, 9. Şirul sortat este 2, 3, 4, 7, 8, 9, 10, 20. Lungimea maximă este 4 (dată de secvenţa 7, 8, 9, 10).