| Fişierul intrare/ieşire: | lumanari.in, lumanari.out | Sursă | Algoritmiada 2013, Runda 4 |
| Autor | Andrei Grigorean, Serban Andrei Stan | Adăugată de |  Serban Andrei Stan •savim |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 9096 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Lumanari
Domnisoarei P. ii plac foarte mult cinele romantice. Ea considera ca o cina este cu atat mai romantica, cu cat sunt aprinse mai multe lumanari la masa la care sta. Proprietarul restaurantului ei favorit stie ca P. ii va trece pragul in urmatoarele seri. Vom numerota aceste seri incepand cu 1. Pentru a o impresiona, el doreste sa aprinda in fiecare seara i exact i lumanari. La sfarsitul serii va stinge lumanarile aprinse. Deasemenea, mai stie ca daca va tine aprinsa o lumanare intr-o seara, inaltimea acesteia va scadea cu 1. El are la dispozitie M lumanari de diferite inaltimi pe care le va folosi numai la masa lui P. Proprietarul vrea sa stie numarul maxim de seri N in care o poate impresiona pe domnisoara P.
Date de intrare
Fişierul de intrare lumanari.in va contine pe prima linie numarul M cu semnificatia din enunt. Pe a doua linie a fisierului de intrare se vor gasi M numere naturale reprezentand inaltimile celor M lumanari.
Date de ieşire
În fişierul de ieşire lumanari.out se va afla valoarea maxima a lui N.
Restricţii
- 1 ≤ M ≤ 200 000
- Inaltimile lumanarilor vor fi numere naturale mai mici ca 109
- Daca o lamanare ajunge la inaltimea 0, nu mai poate fi folosita.
Exemplu
| lumanari.in | lumanari.out |
|---|---|
| 6 1 3 4 5 6 1 | 5 |
Explicaţie
Lumanarile vor fi folosite in urmatorul mod in cele 5 zile:
Ziua 0: 1 3 4 5 6 1
Ziua 1: 0 3 4 5 6 1
Ziua 2: 0 2 3 5 6 1
Ziua 3: 0 2 2 4 5 1
Ziua 4: 0 1 1 3 4 1
Ziua 5: 0 0 0 2 3 0
