小象喜欢玩数组。他有数组 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