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;
vector<int> pos[100060];
int c[100060], a[100060], zd[100060], cnt[100060], res[100060];
struct edge {
  int l, r, id;
} pre[100060];
struct edge1 {
  int st, ed, id;
} q[100060];
struct node {
  int l, r, num, cnt;
} b[4 * 100060];
bool cmp(edge1 a, edge1 b) { return a.ed < b.ed; }
bool cmp1(edge1 a, edge1 b) { return a.id < b.id; }
void build(int l, int r, int i) {
  int mid;
  b[i].l = l;
  b[i].r = r;
  b[i].cnt = 0;
  if (l == r) {
    b[i].num = 0;
    return;
  }
  mid = (l + r) / 2;
  build(l, mid, i * 2);
  build(mid + 1, r, i * 2 + 1);
}
void update(int l, int r, int num, int i) {
  int mid;
  if (b[i].l == l && b[i].r == r) {
    b[i].cnt += num;
    return;
  }
  if (b[i].cnt) {
    b[i * 2].cnt += b[i].cnt;
    b[i * 2 + 1].cnt += b[i].cnt;
    b[i].cnt = 0;
  }
  mid = (b[i].l + b[i].r) / 2;
  if (r <= mid)
    update(l, r, num, i * 2);
  else if (l > mid)
    update(l, r, num, i * 2 + 1);
  else {
    update(l, mid, num, i * 2);
    update(mid + 1, r, num, i * 2 + 1);
  }
}
int question(int id, int i) {
  int mid;
  if (b[i].l == id && b[i].r == id) {
    b[i].num += b[i].cnt;
    b[i].cnt = 0;
    return b[i].num;
  }
  if (b[i].cnt) {
    b[i * 2].cnt += b[i].cnt;
    b[i * 2 + 1].cnt += b[i].cnt;
    b[i].cnt = 0;
  }
  mid = (b[i].l + b[i].r) / 2;
  if (id <= mid)
    return question(id, i * 2);
  else
    return question(id, i * 2 + 1);
}
int main() {
  int n, m, i, j, t, l, r, ind, value;
  while (scanf("%d%d", &n, &m) != EOF) {
    for (i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
    }
    for (i = 1; i <= m; i++) {
      scanf("%d%d", &q[i].st, &q[i].ed);
      q[i].id = i;
    }
    sort(q + 1, q + 1 + m, cmp);
    memset(cnt, 0, sizeof(cnt));
    for (i = 1; i <= n; i++) {
      pos[i].clear();
    }
    build(1, n, 1);
    ind = 1;
    for (i = 1; i <= n; i++) {
      value = a[i];
      if (value <= n) {
        cnt[value]++;
        pos[value].push_back(i);
        if (cnt[value] == value) {
          pre[value].l = 1;
          pre[value].r = pos[value][0];
          pre[value].id = 0;
          update(pre[value].l, pre[value].r, 1, 1);
        } else if (cnt[value] > value) {
          update(pre[value].l, pre[value].r, -1, 1);
          pre[value].id++;
          pre[value].l = pos[value][pre[value].id - 1] + 1;
          pre[value].r = pos[value][pre[value].id];
          update(pre[value].l, pre[value].r, 1, 1);
        }
        while (q[ind].ed == i && ind <= m) {
          res[q[ind].id] = question(q[ind].st, 1);
          ind++;
        }
      }
    }
    sort(q + 1, q + 1 + m, cmp1);
    for (i = 1; i <= m; i++) {
      if (i == m)
        printf("%d\n", res[i]);
      else
        printf("%d ", res[i]);
    }
  }
  return 0;
}
