Description

看到数组就觉得烦躁，因为他学不明白数组。但是今天， 又给 一个数组 来折磨他，这个数组由 个正整数组成，索引从 到 ，我们把索引为 的数字表示为 。 然后 问了 一共 个问题(我们把 提出的一个问题称为一次询问)，每次询问的格式是相同的，包含一对整数 和 。对于每次询问 ， 必须计算有多少个数字 存在，使数字 在数字 中出现的次数大于等于 次。

忙着摸鱼，他现在需要寻求你的帮助。

Input Format

第一行包含两个由空格隔开的整数 ，分别表示数组的长度和问题的个数。 接下来一行包含 个由空格隔开的正整数 。

​接下来 行每行两个整数 和 ，表示一个询问区间。

Output Format

输出共 行，其中第 行表示对第 的问题的回答。

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

2
1​

Hint

在第一个询问中，1出现了3次，2出现了3次，所以答案为2

在第二个询问中，1出现了1次，2出现了1次，所以答案为1