Fişierul intrare/ieşire:secvente2.in, secvente2.outSursăONI 2013, clasa a 9-a
AutorCosmin-Mihai TutunaruAdăugată descipianusFMI Ciprian Olariu scipianus
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Secvente 2

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 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 ai, 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 Li.

Restricţii

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

Exemplu

secvente2.insecvente2.out
8
7
3
2
8
20
4
10
9
1
1
2
2
2
3
3
4

Explicaţie

L1. Şirul: 7. Lungime maximă 1
L2. Şirul: 7,3. Lungime maximă 1
L3. Şirul: 7,3,2. Şirul sortat este 2,3,7. Lungimea maximă este 2 (dată de secvenţa 2,3)
L4. Ş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).
L6. Ş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).
L7. Şirul: 7,3,2,8,20,4,10. Lungime maximă 3 (dată de 2,3,4).
L8. Ş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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content