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>
char in[1 << 22];
struct scanner {
  char const *o;
  char const *e;
  scanner() : o(in) { e = o + fread(in, 1, sizeof(in), stdin); }
  unsigned readInt() {
    while (o != e && *o <= 32) ++o;
    unsigned u = *o++ - '0';
    while (o != e && *o >= '0' && *o <= '9')
      u = (u << 3) + (u << 1) + (*o++ - '0');
    return u;
  }
};
inline int read() {
  register int aa, bb, ch;
  while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-')
    ;
  ch == '-' ? (aa = 0, bb = 1) : (aa = ch - '0', bb = 0);
  while (ch = getchar(), ch >= '0' && ch <= '9')
    aa = (aa << 3) + (aa << 1) + ch - '0';
  return bb ? -aa : aa;
}
const int N = 100010;
int n, m;
struct P {
  int fir, sec, id;
  inline bool operator<(register const P &p) const {
    return fir < p.fir || (fir == p.fir && sec < p.sec);
  }
} q[N];
int t[N];
int a[N], ans[N];
int sum[N], left[N], last[N], next[N], prev[N];
void modify(int p, int d) {
  for (++p; p <= n + 1; p += p & -p) {
    t[p] += d;
  }
}
int query(int l, int r) {
  int ret = 0;
  for (++r; r; r -= r & -r) {
    ret += t[r];
  }
  for (; l; l -= l & -l) {
    ret -= t[l];
  }
  return ret;
}
int main() {
  scanner sc;
  n = sc.readInt();
  m = sc.readInt();
  for (int i = 1; i <= n; ++i) {
    a[i] = sc.readInt();
    if (a[i] <= n) {
      sum[i] = sum[last[a[i]]] + 1;
      if (last[a[i]] == 0) {
        left[i] = i;
        last[a[i]] = i;
      } else {
        left[i] = left[last[a[i]]];
        prev[i] = last[a[i]];
        next[last[a[i]]] = i;
        last[a[i]] = i;
      }
      if (sum[i] > a[i]) {
        --sum[i];
        left[i] = next[left[i]];
      }
    }
  }
  for (int i = 1; i <= m; ++i) {
    q[i].sec = sc.readInt();
    q[i].fir = sc.readInt();
    q[i].id = i;
  }
  ::std::sort(q + 1, q + m + 1);
  for (int i = 1, j = 1; i <= n; ++i) {
    if (sum[i] == a[i] && left[i]) {
      modify(left[i], 1);
      modify(prev[left[i]], -1);
      if (prev[left[i]] != 0) {
        modify(prev[left[i]], -1);
        modify(prev[prev[left[i]]], 1);
      }
    }
    while (j <= m && q[j].fir == i) {
      ans[q[j].id] = query(q[j].sec, q[j].fir);
      ++j;
    }
  }
  {
    char *w = in + sizeof(in);
    for (int i = m; i >= 1; --i) {
      unsigned u = ans[i];
      *--w = '\n';
      do *--w = u % 10 + '0';
      while (u /= 10);
    }
    fwrite(w, 1, in + sizeof(in) - w, stdout);
  }
  return 0;
}
