Little Elephant and Array

题意翻译

小象喜欢和数组玩。现在有一个数组 $a$,含有 $n$ 个正整数,记第 $i$ 个数为 $a_i$。 现在有 $m$ 个询问,每个询问包含两个正整数 $l_j$ 和 $r_j \;(1\leqslant l_j\leqslant r_j\leqslant n)$,小象想知道在 $A_{l_j}$ 到 $A_{r_j}$ 之中有多少个数 $x$,其出现次数也为 $x$。 #### 输入格式 第一行 $n$ 和 $m$, $n$ 表示数组大小, $m$ 表示询问个数; 第二行共 $n$ 个数,第 $i$ 个数为 $a_i$ 的值; 接下来 $m$ 行,每行两个数 $l_j$ 和 $r_j$,意义如题面。 #### 输出格式 共 $m$ 行,每行一个数,表示每一次询问的答案。

题目描述

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_{lj},a_{lj}+1,...,a_{rj} $ . Help the Little Elephant to count the answers to all queries.

输入输出格式

输入格式


The first line contains two space-separated integers $ n $ and $ m $ $ (1<=n,m<=10^{5}) $ — 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}<=10^{9}) $ . 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) $ .

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

3
1