1465. 可莉的蹦蹦炸弹

可莉喜欢带着蹦蹦炸弹出去玩。但之前因为把山炸塌了一块所以被琴团长关在了禁闭室。所以这次,可莉为了了解自己带的 n 个炸弹的特性,将 n 个炸弹排成一行,每个炸弹只会向左跳,且每个炸弹都有自己的跳跃距离,跳到左边的一个炸弹时,被跳到的炸弹也会爆炸向左跳,如此迭代。

每个炸弹爆炸后只会跳到左边的炸弹上,且最左侧的炸弹爆炸后不会继续跳。

为了方便辨认炸弹,从左到右,分别将炸弹编号为 1,2,3,...,n

可莉会问你 m 次问题,每次要问的是:

如果可莉要引爆编号为 r 的炸弹,请问至少多少次爆炸之后,编号为 l 的炸弹或该炸弹左侧的炸弹会爆炸。

输入

第一行两个正整数 n,m \ (2 \leq n \leq 2 \times 10^5,1 \leq m \leq 1 \times 10^5)

第二行有 n-1 个正整数: a_2,a_3,...,a_n ,代表编号为 i 的炸弹爆炸后向左跳会跳到编号为 a_i 的炸弹上。 (1 \leq a_i < i)

之后有 m 行,每行有两个正整数 l,r ,求如果引爆编号为 r 的炸弹,至少多少次爆炸后,编号为 l 的炸弹或其左侧的炸弹会爆炸。 (1 \leq l < r \leq n)

输出

对于每次询问,输出一行数,表示这个询问的答案。

样例

标准输入 复制文本
8 3
1 2 1 3 5 4 6
1 8
2 5
3 4
标准输出 复制文本
5
2
1

来源

2021 软件学院 ACM 集训队筛选赛

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 139
通过 27