‹ 上一题下一题 ›

j01281. 跳跃游戏 II 未做

1000 ms 256 MB 测试点 10 通过率 20% 5级·贪心经典模型贪心贪心与排序/堆的配合

文件读写输入j01281.in输出j01281.out

题目描述

一排 $n$ 个格子，第 $i$ 格的跳跃力为 $a_{i}$ ：站在格 $i$ 可以向右跳 $1$ 到 $a_{i}$ 格。从格 $1$ 出发要到达格 $n$ ，求最少跳跃次数（数据保证可达； $n = 1$ 时输出 $0$ ）。

输入格式

第一行一个整数 $n$ ；第二行 $n$ 个整数 $a_{i}$ 。

输出格式

一行一个整数：最少跳跃次数。

样例

输入

5
2 3 1 1 4

输出

数据范围

$1 \leq n \leq 1 0^{5}$ ， $1 \leq a_{i} \leq 1 0^{5}$ ；数据保证可达

输入

输出

答案