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 \leq n \leq 10^6)$.
• Dòng hai chứa $n$ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \leq a_i \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 \rightarrow 2 \rightarrow 5$.

Tính điểm

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