暂无测试数据。

Background

Description

crf 从小就显现出了过人的天赋，他出生的第三天就证明了哥德巴赫猜想，第五天就证明了质能方程，出生一星期之后，他觉得 P 是否等于 NP 这个问题比前面他证明的这些定理好玩多了，于是他成为了一名计算机科学家。
在他开始接触计算机科学的第一天，他就已经刷遍了所有 oj，这为他今后建立王国推行全民刷题计划打下了坚实的基础。在他接触计算机科学一星期之后，他就已经通读了所有顶会 paper，并且在多方面同时出了许多成果。
他对他王国的国民智商有非常高的要求，他为想加入他的王国国籍的人准备了很多试题去测试智商，但因为他接触计算机科学第一天学到的东西就已经超过正常人一生的水平了，所以他出的试题水平在他接触计算机科学 1 分钟以内的水平。
这道题是 crf 接触计算机科学第 17 秒想出的问题。
crf 拥有一个长度为 n 的数字序列，他向你询问了 q 个问题，每个问题都是告诉你两个数 l 和r，问你在序列的第 l 到第 r 个数的这一段序列中，有多少个数字 k，满足在这一段中恰好出现了 k次。

Format

Input

输入的第一行为两个整数 n, q，表示序列的长度和问题的个数。
接下来一行有 n 个整数，表示 crf 的数字序列。
接下来 q 行，每行有两个整数 l, r，其含义如题目中所示。

Output

输出共 q 行，每行有一个整数，表示第 i 个问题的答案。

Sample

Input

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

Output

3
1

Limitation

对于 30% 的数据，保证 1 ≤ n, q ≤ 100。
对于 70% 的数据，保证 1 ≤ n, q ≤ 100000。
对于 100% 的数据，保证 1 ≤ n, q ≤ 1000000, 序列中的每个数都在 [1, n] 范围内。
3s, 256000KiB for each test case.

Hint

Source

CDQZ TEST