Sau khi đi lang thang, Alice bị lạc vào 1 công viên kì lạ, chứa ~n~ tấm bạt lò xo được xếp thành ~1~ hàng. Tấm bạt lò xo thứ ~i~ có độ nảy là ~S_i~.

Alice có thể nhảy trên các tấm bạt lò xo nhiều lần. Cô bắt đầu một lượt nhảy bằng cách nhảy lên bất kì tấm bạt lò xo nào mà mình chọn.

Nếu Alice nhảy lên tấm bạt lò xo thứ ~i~, cô sẽ bay đến vị trí ~i + S_i~ và độ nảy của tấm bạt lò xo thứ ~i~ sẽ bị hao hụt đi ~1~. Vì các tấm bạt lò xo luôn có độ nảy dù ít hay nhiều, nên ~S_i~ luôn lớn hơn hoặc bằng ~1~ trong mọi thời điểm. Nói cách khác, khi Alice nhảy lên tấm bạt lò xo thứ ~i~, thì ~S_i = max(S_i - 1, 1)~. Nếu không có tấm bạt lò xò nào ở vị trí ~i + S_i~, thì lượt nhảy hoàn thành. Ngược lại, Alice sẽ tiếp tục lượt bằng cách nhảy khỏi tấm bạt ở vị trí ~i + S_i~, theo nguyên tắc được mô tả ở trên.

Alice không thể kết thúc lượt cho đến khi cô ấy đáp ở vị trí lớn hơn ~n~. Với tính cách nghịch ngợm của mình, cô cảm thấy phấn khích với điều đó. Cô muốn phá hủy công viên lò xo bằng cách giảm độ nảy của toàn bộ ~n~ tấm bạt xuống ~1~. Vì không giỏi tính toán, Alice muốn hỏi bạn liệu cô ấy cần ít nhất bao nhiêu lượt nhảy để có thể phá hủy được công viên. Hãy giúp Alice nhé!

Input

Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 10^6~) — độ dài của công viên.

Dòng thứ hai gồm ~n~ số nguyên dương ~S_1, S_2, \ldots, S_n~ (~1 \le S_i \le 10^9~) — độ nảy của ~n~ tấm bạt lò xo.

Output

Ghi ra trên một dòng là số lượt ít nhất Alice cần phải nhảy.

Sample Input 1

7
1 4 2 2 2 2 2

Sample Output 1

4

Notes

Trình tự nhảy tối ưu được thể hiện bên dưới (vị trí các tấm bạt lò xo mà Alice nhảy lên trong mỗi lượt được in đậm)

[1, 4, 2, 2, 2, 2, 2]

[1, 3, 2, 2, 2, 1, 2]

[1, 2, 2, 2, 1, 1, 1]

[1, 1, 2, 1, 1, 1, 1]