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;
namespace FastIO {
const int SIZE = 1 << 22;
char Str1[SIZE + 5], Str2[SIZE + 5], *P1 = Str1, *P2 = Str1, *Temp = Str2,
                                     Tmp[110];
inline char Getchar() {
  return P1 == P2 ? (P2 = (P1 = Str1) + fread(Str1, 1, SIZE, stdin),
                     P1 == P2 ? EOF : *P1++)
                  : *P1++;
}
inline void Flush() {
  fwrite(Str2, 1, Temp - Str2, stdout), Temp = Str2;
  return;
}
inline void Putchar(char Ch) {
  *Temp++ = Ch;
  if (Temp - Str2 == SIZE) {
    Flush();
  }
  return;
}
template <class T>
inline void Read(T &x) {
  char Ch = Getchar();
  T f = 1;
  x = 0;
  while (Ch < '0' or Ch > '9') {
    f = Ch == '-' ? -1 : f, Ch = Getchar();
  }
  while (Ch >= '0' and Ch <= '9') {
    x = (x << 1) + (x << 3) + (Ch ^ 48), Ch = Getchar();
  }
  x *= f;
  return;
}
template <class T>
inline void Write(T x, char Ch = '\n') {
  if (x == 0) {
    Putchar('0'), Putchar(Ch);
    return;
  }
  register int Count = 0;
  while (x) {
    Tmp[++Count] = (x % 10) ^ 48, x /= 10;
  }
  while (Count) {
    Putchar(Tmp[Count--]);
  }
  Putchar(Ch);
  return;
}
struct Node {
  ~Node() { Flush(); }
} f;
}  // namespace FastIO
using namespace FastIO;
const int MAXN = 1e6 + 10;
int w[MAXN], bl[MAXN], Ans[MAXN], num[MAXN], ans = 0, n, q, s;
struct node {
  int fir, sec, id;
} Ask[MAXN];
bool cmp(node x, node y) {
  return (bl[x.fir] ^ bl[y.fir])
             ? (x.fir < y.fir)
             : ((bl[x.fir] ^ 1) ? (x.sec < y.sec) : (x.sec > y.sec));
}
void Del(int x) {
  if (x <= n) {
    if (num[x] == x) {
      --ans;
    }
    --num[x];
    if (num[x] == x) {
      ++ans;
    }
  }
}
void Add(int x) {
  if (x <= n) {
    if (num[x] == x) {
      --ans;
    }
    ++num[x];
    if (num[x] == x) {
      ++ans;
    }
  }
}
int main() {
  int i;
  Read(n), Read(q), s = sqrt(n);
  for (i = 1; i <= n; ++i) {
    Read(w[i]);
    bl[i] = (i - 1) / s + 1;
  }
  for (i = 1; i <= q; ++i) {
    Read(Ask[i].fir), Read(Ask[i].sec), Ask[i].id = i;
  }
  sort(Ask + 1, Ask + 1 + q, cmp);
  int l = 1, r = 0, ql, qr;
  for (i = 1; i <= q; ++i) {
    ql = Ask[i].fir, qr = Ask[i].sec;
    while (l < ql) {
      Del(w[l++]);
    }
    while (r < qr) {
      Add(w[++r]);
    }
    while (l > ql) {
      Add(w[--l]);
    }
    while (r > qr) {
      Del(w[r--]);
    }
    Ans[Ask[i].id] = ans;
  }
  for (i = 1; i <= q; ++i) {
    Write(Ans[i]);
  }
  return 0;
}
