Se citesc n copii asezati la rand, fiecare cu un rating. Fiecare copil trebuie sa primeasca cel putin o bomboana; un copil cu rating strict mai mare decat un vecin (stanga sau dreapta) trebuie sa primeasca strict mai multe bomboane decat acel vecin. Determinati, folosind metoda Greedy, numarul minim total de bomboane necesare.
- Date de intrare
- Pe prima linie se citeste n. Pe a doua linie se citesc cele n ratinguri.
- Date de iesire
- Se afiseaza un singur numar: numarul minim total de bomboane.
- Restrictii
- 1 <= n <= 100000, 0 <= rating <= 10^9
Exemple
Exemplul 1
Intrare
3 1 0 2
Iesire
5
Exemplul 2
Intrare
3 1 2 2
Iesire
4