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 ai. 

Additionally the Little Elephant has m queries to the array, each query is characterised by a pair of integers lj and rj (1 ≤ lj ≤ rj ≤ n). For each query lj, rj the Little Elephant has to count, how many numbers x exist, such that number x occurs exactly x times among numbers alj, alj + 1, ..., arj.

Help the Little Elephant to count the answers to all queries.

Input

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 105) — the size of array a and the number of queries to it. The next line contains n space-separated positive integers a1, a2, ..., an (1 ≤ ai ≤ 109). 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 lj and rj (1 ≤ lj ≤ rj ≤ n).

Output

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

Examples

Input

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


Output

3
1
#include <bits/stdc++.h>
using namespace std;
map<int, int> match;
int tree[100010], n, m, num, ans[100010], val[100010], f[100010], p[100010];
vector<int> vc[100010];
struct node {
  int l, r, pos;
} op[100010];
bool cmp(node a, node b) { return a.r < b.r; }
int lowbit(int x) { return x & (-x); }
void update(int x, int val) {
  for (; x <= n; x += lowbit(x)) tree[x] += val;
}
int query(int x) {
  int ret = 0;
  for (; x > 0; x -= lowbit(x)) ret += tree[x];
  return ret;
}
int main() {
  int i, j, k, pos;
  scanf("%d%d", &n, &m);
  for (i = 1; i <= n; i++) {
    scanf("%d", &val[i]);
    f[i] = val[i];
  }
  sort(f + 1, f + 1 + n);
  for (i = 1; i <= n; i++)
    if (f[i] != f[i - 1]) {
      num++;
      match[f[i]] = num;
    }
  for (i = 1; i <= m; i++) {
    scanf("%d%d", &op[i].l, &op[i].r);
    op[i].pos = i;
  }
  for (i = 1; i <= num; i++) vc[i].push_back(0);
  sort(op + 1, op + 1 + m, cmp);
  op[m + 1].r = 0;
  pos = 1;
  for (i = 1; i <= n; i++) {
    k = match[val[i]];
    p[k]++;
    vc[k].push_back(i);
    if (p[k] >= val[i]) {
      update(vc[k][p[k] - val[i]] + 1, 1);
      update(vc[k][p[k] - val[i] + 1] + 1, -1);
      if (p[k] > val[i]) {
        update(vc[k][p[k] - val[i] - 1] + 1, -1);
        update(vc[k][p[k] - val[i]] + 1, 1);
      }
    }
    while (op[pos].r == i) {
      ans[op[pos].pos] = query(op[pos].l);
      pos++;
    }
  }
  for (i = 1; i <= m; i++) printf("%d\n", ans[i]);
}
