问题 C: 简单跳跃

问题 C: 简单跳跃

时间限制: 1 Sec  内存限制: 128 MB
提交: 467  解决: 181
[提交][状态][讨论版][命题人:]

题目描述

有n个格子排成一排,一枚棋子,最初在第一个格子上(最左边的格子为第一个格子),每个格子上有一个数字a,表示在该格子上一步最多可以往后跳a格,现给出n个格子及每个格子上的数字,求出从第一个格子跳到最后一个格子所需最小步数。

如图所示:

共五个格子,其各个值为2,3,1,1,4,棋子可以从第一个格子跳到第二个格子,再从第二个格子跳到第五个格子,即可走2步到最后一个格子。

输入

第一行一整数n
随后一行n个整数ai,表示格子从左到右每个格子上的数值
2<=n<=1000
0<=ai<=109

输出

一行一个整数表示最小步数,如果不能跳到最后一个格子,输出-1

样例输入

5
2 3 1 1 4

样例输出

2

提示

[提交][状态]