普及⏱ 1000ms💾 256MB#P5050

题目描述

数组每个位置有一个最大跳跃长度 $a_i$:站在下标 $i$ 可以跳到 $i+1..i+a_i$ 中任意位置。从下标 $0$ 出发要到达最后一格($n-1$),输出最少跳跃次数;无法到达输出 -1。起点即终点时次数为 $0$

输入格式

第一行整数 $n$;第二行 $n$ 个非负整数。

输出格式

一行一个整数。

数据范围

$$1 \le n \le 10^5,\ 0 \le a_i \le 10^5$$

样例输入 #1
1
0
样例输出 #1
0
样例输入 #2
2
1 0
样例输出 #2
1