markdown

B. 小象与数组

时间限制：每个测试点 $4$ 秒
内存限制：每个测试点 $256$ MB
输入：标准输入
输出：标准输出

小象喜欢玩数组。他有一个由 $n$ 个正整数组成的数组 $a$，下标从 $1$ 到 $n$。记下标为 $i$ 的数为 $a_i$。

此外，小象有 $m$ 个关于该数组的查询，每个查询由两个整数 $l_j$ 和 $r_j$（$1 \le l_j \le r_j \le n$）描述。对于每个查询 $l_j, r_j$，小象需要统计：有多少个数 $x$ 满足在 $a_{l_j}, a_{l_j+1}, \dots, a_{r_j}$ 中，$x$ 恰好出现了 $x$ 次。

请帮助小象计算所有查询的答案。

输入

第一行包含两个空格分隔的整数 $n$ 和 $m$（$1 \le n, m \le 10^5$）—— 数组 $a$ 的大小和查询的数量。
第二行包含 $n$ 个空格分隔的正整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。
接下来 $m$ 行每行描述一个查询，第 $j$ 行包含两个空格分隔的整数 $l_j$ 和 $r_j$（$1 \le l_j \le r_j \le n$）。

输出

输出 $m$ 行，每行一个整数 —— 对应查询的答案。第 $j$ 行应输出第 $j$ 个查询的答案。

示例

输入

7 2
3 1 2 2 3 3 7
1 7
3 4

输出

3
1