小 A 的消息记录中有 n 条消息，依次以 1, 2, \dots, n 编号。编号小的消息发送时间早于编号大的消息。

一条消息可以引用一条编号小于它的消息，也可以不引用消息。小 A 注意到消息记录里有引用的消息数量不会非常多。消息记录的一个例子是：

• 【消息 1】小 A：有人做了今天的第一题吗？
• 【消息 2】小 A：我第一题 WA 了，可能是什么原因？
• 【消息 3：引用消息 1】小 B：我我我
• 【消息 4：引用消息 2】小 C：我也 WA 了
• 【消息 5：引用消息 2】小 B：是不是没开 long long？
• 【消息 6：引用消息 5】小 A：改了就 AC 了，太厉害了！

对于消息 i (1 \le i \le n)，小 A 以 r_i 标记消息 i 是否有引用，以及所引用的消息编号。如果 r_i > 0，则消息 i 为引用了消息 r_i；如果 r_i = 0，则消息 i 没有引用消息。

消息记录里有非常多条消息。为了快速查找所需要的消息，小 A 准备实现一个简单的消息查找工具。消息查找工具任意时刻只能定位恰好一条消息，如果当前位于消息 i (1 < i \le n)，那么接下来可以选择以下两种操作之一：

• 定位到消息 i - 1；
• 如果消息 i 引用了消息 r_i，定位到消息 r_i。

以上操作可以执行任意次（包括零次）。

小 A 有 q 次询问。在第 k (1 \le k \le q) 次询问中，小 A 给出消息编号 x_k, y_k (y_k < x_k)。小 A 想知道，如果当前消息查找工具位于 x_k，至少需要多少次操作才能定位到消息 y_k。

第一行，两个正整数 n, q，分别表示消息条数与询问次数。

第二行，n 个非负整数 r_1, r_2, \dots, r_n，表示消息的引用关系，具体含义见题目描述。

接下来 q 行中的第 k 行 (1 \le k \le q) 包含两个正整数 x_k, y_k，表示一次询问。

保证至多只有 1000 条引用消息。

输出 q 行，每行一个整数，表示将界面从消息 x_k 切换到消息 y_k 所需的最少操作次数。

数据范围

对于 40% 的测试点，保证 1 \le n \le 2000，1 \le q \le 2000。

对于所有测试点，保证 1 \le n \le 10^5，1 \le q \le 10^5，0 \le r_i < i，1 \le y_k < x_k \le n，保证至多有 1000 条引用消息。