Numim secventa progresiva a unui sir crescator de numere naturale un subsir al acestuia, format din termeni aflati pe pozitii consecutive in sirul dat, cu proprietatea ca fiecare termen apare in subsir de un numar de ori egal cu valoarea sa. Lungimea secventei este egala cu numarul de termeni ai acesteia.
Fisierul bac.txt contine un sir crescator de cel mult 10^6 numere naturale din intervalul [1,10^6], astfel incat orice termen al sirului apare de un numar de ori cel mult egal cu valoarea sa. Numerele sunt separate prin cate un spatiu.
Se cere sa se afiseze pe ecran lungimea maxima a unei secvente progresive din sirul aflat in fisier. Proiectati un algoritm eficient din punctul de vedere al timpului de executare si al memoriei utilizate.
Exemplu: daca fisierul contine numerele 1 2 2 3 4 4 4 4 6 6 6 6 6 6 7 7 7 8 8 8 8 8 8 8 8 atunci pe ecran se afiseaza valoarea 10.
- Date de intrare
- Fisierul bac.txt: un sir crescator de numere naturale din [1,10^6].
- Date de iesire
- Se afiseaza lungimea maxima a unei secvente progresive.
- Restrictii
- sirul are cel mult 10^6 termeni, valori in [1, 10^6]
Exemple
Exemplul 1
Intrare
1 2 2 3 4 4 4 4 6 6 6 6 6 6 7 7 7 8 8 8 8 8 8 8 8
Iesire
10
Exemplul 2
Intrare
1 1
Iesire
0