题目描述

给定一个非负整数数组nums,青蛙最初位于数组的第一个元素(下标为0),数组中的每个元素表示它在该位置可以跳跃的最大长度,请求出它所能跳跃到的最远下标。


输入格式

第一行一个整数N,表示数组nums的大小
接下来一行N个整数,表示数组nums


输出格式

仅输出一行一个整数,表示青蛙所能跳跃到的最远下标


样例数据

输入

Input1:
5
2 3 1 1 4

Input2:
5
3 2 1 0 4

Input3:
5
1 4 3 3 2

输出

Output1:
4

Output2:
3

Output3:
4

备注

数据范围:
$1 \leq N \leq 10^5, 0 \leq nums[i] \leq 10^5$
样例解释:
对于样例1:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标4;
对于样例2:可以先跳 3 步,从下标 0 到达下标3;
对于样例3:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标4


信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

导航

比赛介绍
比赛排名
数据统计
评测状态
答疑平台
打印服务