Considerăm şirul de numere naturale nenule distincte a1, a2, ..., aN. Notăm cu Li 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: L1 = 1, L2 = 1, L3 = 2, L4 = 2, L5 = 2, L6 = 3, L7 = 3, L8 = 4.
Cerinţă
Să se determine L1, L2, ..., LN.
Date de intrare
Fişierul secvente2.in conţine pe prima linie numărul natural N. Pe fiecare dintre următoarele N linii se găseşte câte un număr natural, deci pe linia i+1 se va afla elementul ai, pentru i=1...N.
Date de ieşire
Fişierul secvente2.out va conţine exact N linii. Pe linia i (i = 1...N) se va afişa valoarea Li.
Restricţii
• 3 ≤ N ≤ 190 000
• 1 ≤ ai ≤ 1 000 000, pentru orice i = 1...N
Exemple
secvente2.in
secvente2.out
Explicaţii
8
7
3
2
8
20
4
10
9
1
1
2
2
2
3
3
4
L 1. Şirul : 7. Lungime maximă 1
L2. Şirul: 7,3. Lungime maximă 1
L 3. Ş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)
L5. Ş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).