salturi

Se dă un șir de numere întregi $a_0, a_1, \dots, 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$, $\dots$, $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$, $\dots$, $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ţă

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, 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 \leq N \leq 1 \ 000 \ 000$
• $-1 \ 000 \ 000 \leq a_i \leq 1 \ 000 \ 000$, pentru fiecare $0 \leq i \leq N - 1$.
• Întotdeauna este posibil să se ajungă la o poziţie mai mare decât $N - 1$.
• Concurenţilor care scriu programe C/C++ li se recomandă să citească datele de intrare cu ajutorul funcţiilor din biblioteca C.

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.