O gradina este reprezentata ca segmentul [0,n] pe o axa. Exista n+1 robinete, robinetul i (0 <= i <= n) fiind situat la pozitia i; daca este deschis, el uda intervalul [i-raza[i], i+raza[i]] (limitat la [0,n]). Determinati, folosind metoda Greedy, numarul minim de robinete ce trebuie deschise pentru a uda intreaga gradina. Daca acest lucru nu este posibil, afisati -1.
- Date de intrare
- Pe prima linie se citeste n. Pe a doua linie se citesc cele n+1 valori raza[0], raza[1], ..., raza[n].
- Date de iesire
- Se afiseaza un singur numar: numarul minim de robinete necesare, sau -1 daca gradina nu poate fi udata in intregime.
- Restrictii
- 1 <= n <= 10000, 0 <= raza[i] <= n
Exemple
Exemplul 1
Intrare
5 3 4 1 1 0 0
Iesire
1
Exemplul 2
Intrare
3 0 0 0 0
Iesire
-1