Gấu có nuôi một con ếch có khả năng nhảy bật rất giỏi. Tại vị trí $i$, con ếch có thể nhảy tới vị trí bất kỳ từ $i+1$ đến $i+a_i$. Hãy tìm cách để con ếch nhảy ít bước nhất đến vị trí $n$.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$ $(1\le n\le {10}^6)$.
• Dòng hai chứa $n$ số nguyên ~a1, a2, \dots, an~ ~(1 \leq ai \leq 10^9)~.

Dữ liệu ra

Gồm một số duy nhất là đáp án của bài toán.

Ví dụ

Đầu vào

5
2 3 1 4 2

Đầu ra

2

Giải thích

Con ếch sẽ nhảy như sau: $1\to 2\to 5$.

Tính điểm

• Subtask $1$ $(50\%$ số điểm$)$: $1\le n\le 1000$.
• Subtask $2$ $(50\%$ số điểm$)$: Không có ràng buộc gì thêm.