← 返回题目列表

Codeforces · 220/B

B. 小象和阵列

中文机器翻译题面 查看原题

小象喜欢玩数组。他有数组 a,由 n 个正整数组成,索引从 1 到 n。我们将索引为 i 的数字表示为 ai。

另外,小象对数组有 m 个查询,每个查询都由一对整数 lj 和 rj 来表征(1 ≤ lj ≤ rj ≤ n)。对于每个查询 lj, rj,小象必须计算存在多少个数字 x,使得数字 x 在数字 alj, alj + 1, ..., arj 中恰好出现 x 次。

帮助小象数出所有问题的答案。

输入

第一行包含两个以空格分隔的整数 n 和 m (1 ≤ n, m ≤ 105) — 数组 a 的大小及其查询次数。下一行包含 n 个空格分隔的正整数 a1, a2, ..., an (1 ≤ ai ≤ 109)。接下来的 m 行包含查询的描述,每行一个。这些行的第 j 行包含第 j 个查询的描述,作为两个空格分隔的整数 lj 和 rj (1 ≤ lj ≤ rj ≤ n)。

输出

在 m 行中打印 m 个整数 — 查询的答案。第 j 行应包含第 j 个查询的答案。

示例

输入 #1

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

输出 #1

3
1