CF220B.Little Elephant and Array

The Little Elephant loves playing with arrays. He has array a, consisting of n positive integers, indexed from 1 to n. Let's denote the number with index i as a__i.

Additionally the Little Elephant has m queries to the array, each query is characterised by a pair of integers l__j and r__j (1 ≤ l__j ≤ r__j ≤ n). For each query l__j, r__j the Little Elephant has to count, how many numbers x exist, such that number x occurs exactly x times among numbers a__l__j, a__l__j + 1, ..., a__r__j.

Help the Little Elephant to count the answers to all queries.

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

此外，小象还有 $m$ 个针对该数组的查询，每个查询由一对整数 $l_j$ 和 $r_j$（满足 $1 \leq l_j \leq r_j \leq n$）表征。对于每个查询 $(l_j, r_j)$，小象需要统计：有多少个数 $x$ 满足——$x$ 在子数组 $a_{l_j}, a_{l_j+1}, ..., a_{r_j}$ 中恰好出现 $x$ 次。

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

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 105) — the size of array a and the number of queries to it. The next line contains n space-separated positive integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109). Next m lines contain descriptions of queries, one per line. The j-th of these lines contains the description of the j-th query as two space-separated integers l__j and r__j (1 ≤ l__j ≤ r__j ≤ n).

第一行包含两个以空格分隔的整数 $n$ 和 $m$（$1 ≤ n, m ≤ 10^5$），分别表示数组 $a$ 的大小以及对其执行的查询次数。
第二行包含 $n$ 个以空格分隔的正整数 $a_1, a_2, \dots, a_n$（$1 ≤ a_i ≤ 10^9$）。
接下来的 $m$ 行每行描述一个查询，共 $m$ 行。其中第 $j$ 行包含第 $j$ 个查询的描述，即两个以空格分隔的整数 $l_j$ 和 $r_j$（$1 ≤ l_j ≤ r_j ≤ n$）。

In m lines print m integers — the answers to the queries. The j-th line should contain the answer to the j-th query.

在 m 行中输出 m 个整数——即各查询的答案。第 j 行应包含第 j 个查询的答案。