题目描述

给出一棵 $n$ 个点的有根树。

$q$ 次询问，每次给出 $l$、$r$，表示询问树上总共有多少个点，满足其子树包含 $[l,r]$ 中的至少一个点。

输入格式

输入的第一行包含两个数 $n$、$q$。

第二行包含 $n$ 个数 $f_{1 \dots n}$，$f_i$ 表示 $i$ 在树上的父亲。若 $i$ 为根，则 $f_i=0$。

接下来 $q$ 行，每行包含两个数 $l$、$r$，表示一次询问。

输出格式

输出应包含 $q$ 行，第 $i$ 行包含一个数，表示你对第 $i$ 次询问求出的答案。

样例数据

样例 1 输入

5 6
3 0 2 2 3
1 1
4 5
1 4
3 5
1 5
2 4

样例 1 输出

3
4
4
4
5
3

样例 2~5

见下发文件。

数据规模与约定

对于所有数据，有 $1 \le n \le 5 \times 10^5$，$1 \le q \le 10^5$，$0 \le f_i \le n$，$1 \le l \le r \le n$。