Se dă un șir de numere întregi a[0],a[1],..a[N-1]. Fiecare valoare a[i] reprezintă mărimea maximă a unui salt ce poate fi efectuat din pozitia i. Din poziţia i, se poate ajunge printr-un salt la oricare din poziţiile i+1, i+2,…, i+a[i], dacă a[i] este pozitiv, iar dacă a[i] este negativ se poate ajunge la oricare din poziţiile i-1,i-2,…, i+a[i].

Trebuie să se ajungă, prin salturi, de la poziția 0 la o poziție mai mare decât N-1 (în afara vectorului, la dreapta).

Cerința

Scrieți un program care să determine numărul minim de salturi necesare pentru a ajunge de la poziția 0 la o poziție mai mare decât N-1.

Date de intrare

Fișierul de intrare salturi.in conține pe prima linie numărul natural N. Pe linia a doua se află scrise cele N numere ale șirului a[], separate prin spații.

Date de ieșire

Fișierul de ieșire salturi.out va conține un singur număr natural reprezentând numărul minim de salturi necesare pentru a ajunge de la poziția 0 la o poziție mai mare decât N-1.

Restricții și precizări

• 2 ≤ N ≤ 1.000.000
• -1000 000 ≤ a[i] ≤ 1.000.000, pentru fiecare 0 ≤ i ≤ N-1.
• Întotdeauna este posibil să se ajungă la o poziţie mai mare decât N-1.

Exemplu:

salturi.in

5
2 3 -10 1 1

salturi.out

3

Explicație

De la poziția 0 se sare la poziția 1, apoi la poziția 4, apoi în afara șirului.