Fişierul intrare/ieşire:	secvente2.in, secvente2.out	Sursă	ONI 2013, clasa a 9-a
Autor	Cosmin-Mihai Tutunaru	Adăugată de	FMI Ciprian Olariu •scipianus
Timp execuţie pe test	0.1 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Secvente 2

Considerăm şirul de numere naturale nenule distincte a₁, a₂, ..., 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, L₂ = 1, L₃ = 2, L₄ = 2, L₅ = 2, L₆ = 3, L₇ = 3, L₈ = 4.

Cerinţă

Să se determine L₁, L₂, ..., L_N.

Date de intrare

Fişierul de intrare secvente2.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

În fişierul de ieşire secvente2.out conţine exact N linii. Pe linia i (i = 1...N) se va afişa valoarea L_i.

Restricţii

• 3 ≤ N ≤ 200 000
• 1 ≤ a_i ≤ 1 000 000, pentru orice i = 1...N
• Pentru 35% din teste se garantează că N ≤ 1000

Exemplu

Explicaţie

L₁. Şirul: 7. Lungime maximă 1
L₂. Şirul: 7,3. Lungime maximă 1
L₃. Şirul: 7,3,2. Şirul sortat este 2,3,7. Lungimea maximă este 2 (dată de secvenţa 2,3)
L₄. Şirul: 7,3,2,8. Lungime maximă 2 (dată de 2,3)
L₅. Şirul: 7,3,2,8,20. Lungime maximă 2 (dată de 2,3).
L₆. Ş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₇. Şirul: 7,3,2,8,20,4,10. Lungime maximă 3 (dată de 2,3,4).
L₈. Ş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).

Cum se trimit solutii?