普及-⏱ 1000ms💾 256MB#P3086

题目描述

数组每个位置有一个最大跳跃长度 $a_i$(从下标 $i$ 可以跳到不超过 $i+a_i$ 的任意更靠后位置)。从下标 $0$ 出发,判断能否到达最后一格;若能,输出最少跳跃次数。

输入格式

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

输出格式

能到达则输出一行最少次数;否则输出 -1

数据范围

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

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