题目描述
有 n 个格子排成一排,编号为 1,2,…,n。第 i 个格子有一个跳跃力 ai。从格子 i 出发,可以跳到区间
[i+1, min(n, i+ai)]
中的任意一个格子。
有 q 次询问,每次给出起点 s 和终点 t,满足 s<t。求从 s 跳到 t 最少需要跳几次。保证对于每次询问,从 s 一定可以到达 t。
输入格式
第一行两个整数 n,q。
第二行 n 个整数 a1,a2,…,an。
接下来 q 行,每行两个整数 s,t,表示一次询问。
输出格式
输出 q 行,每行一个整数,表示对应询问的最少跳跃次数。
5 3
2 3 1 1 1
1 5
1 4
2 5
2
2
1
样例解释
- 询问 1→5:可以 1→2→5,共 2 步。
- 询问 1→4:可以 1→2→4,共 2 步。
- 询问 2→5:因为 2+a2=5,可以直接 2→5,共 1 步。
数据范围
对于 100% 的数据:
1≤n,q≤2×105,n>1
1≤ai≤n
1≤s<t≤n
保证每次询问从 s 一定能到达 t。