题目描述

定义一个数组 $b_0,b_1,\dots,b_{M-1}$ 是自描述数组，当且仅当对于数组中的每个元素 $b_i$，数值 $b_i$ 在整个数组中恰好出现 $b_i$ 次。

例如：

• [1, 2, 2] 是自描述数组；
• [5, 5, 5, 5, 5] 是自描述数组；
• [3, 1, 3, 2, 3, 2] 是自描述数组；

而下面这些不是：

• [100, 1, 2, 2] 不是，因为 100 只出现了 1 次；
• [1, 1, 1, 1, 1] 不是，因为 1 出现了 5 次。

进一步地，若数组 $b_l,b_{l+1},\dots,b_r$ 本身是自描述数组，则称它为一个自描述子数组。

给定一个数组 $a_0,a_1,\dots,a_{N-1}$，以及 $Q$ 次询问 $(l,r)$（满足 $l \le r$）。

对于每次询问，你需要求出有多少个子数组 $(l',r')$ 满足：

• $l \le l' \le r' \le r$；
• 子数组 $a_{l'}, a_{l'+1}, \dots, a_{r'}$ 是自描述子数组。

实现方式

你需要实现以下两个过程：

初始化

void init(int N, int Q, const std::vector<int>& a)

该函数在每个测试点中只会被调用一次，传入原数组 $a$。

单次询问

long long query(int l, int r)

该函数会被调用 $Q$ 次，每次对应一个区间询问 $(l,r)$，你需要返回答案。

本地测试

本地 grader 会按如下格式读入数据：

1. $N,Q$
2. 数组 $a_0,a_1,\dots,a_{N-1}$
3. 接下来 $Q$ 行，每行一个询问 $(l,r)$

然后它会先调用 init，再依次调用 query 并输出答案。

你可以自由修改本地 grader。

数据范围

• $1 \le N, Q \le 3 \times 10^5$
• $1 \le a_i \le N$
• $0 \le l \le r \le N-1$

样例

输入

7 3
1 2 1 2 3 3 3
0 3
2 6
0 6

输出

3
2
5

子任务

只有通过某个子任务及其依赖的全部测试，才能获得该子任务分数。