HZNUOJ

KK玩跳一跳

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:349     AC:77     Score:96.46

Description

      还记得最近很火的小游戏跳一跳吗,KK很喜欢玩,手指在屏幕上点的时间就是蓄力时间,是不是很难玩呢?现在有一个跳一跳的简化版,规则的描述是这样的。

      总共有n个格子,每个格子都有一个数字Ai,代表在这个格子上能跳的最远距离是Ai,比如如果一个格子上的数字是3,代表你可以往后跳1,格,2格,或者3格。一开始你是站在第一个格子上,游戏通关的方法是跳到第n个格子。所以这个游戏一定能通关,但是通关后会有一个评分,这个评分是n减去跳跃总步数,KK现在希望你写一个作弊程序,保证每次得到的分数最大。

Input

      第一行是n,代表有n个格子。(n<=10000)

      第二行是n个整数,代表第i个格子最远能跳跃的距离。最大的跳跃距离小于等于100.

Output

最大的分数

Samples

input
5 3 1 1 1 1
output
3

Hint

对于样例:

5
3 1 1 1 1
第一步跳到第四格,再跳到第五格,总共跳两次,所以是5-2=3

Author

YU, Saikang

Source

2018春学期ACM通识课期末考试