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;
void read_file(bool outToFile = true) {}
int n, nq;
const int MAXN = 100000 + 9;
int A[MAXN];
map<int, int> mp;
map<int, int>::iterator it;
int rmp[MAXN];
struct queryy {
  int l, r, i, b;
  queryy(int nl = 0, int nr = 0, int ni = 0, int nb = 0) {
    l = nl, r = nr, i = ni, b = nb;
  }
  bool operator<(queryy oth) const {
    if (b != oth.b) return b < oth.b;
    if (b & 1)
      return r > oth.r;
    else
      return r < oth.r;
  }
};
const int nMax = MAXN;
queryy Q[nMax];
int sqrtn;
int cnt[nMax];
int ans[nMax];
int curans;
void add(int idx) {
  int encode = mp[A[idx]];
  if (cnt[encode] == A[idx]) curans--;
  cnt[encode]++;
  if (cnt[encode] == A[idx]) curans++;
}
void del(int idx) {
  int encode = mp[A[idx]];
  if (cnt[encode] == A[idx]) curans--;
  cnt[encode]--;
  if (cnt[encode] == A[idx]) curans++;
}
void MO() {
  for (int i = 0; i < nq; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    l--, r--;
    Q[i] = queryy(l, r, i, l / sqrtn);
  }
  sort(Q, Q + nq);
  memset(cnt, 0, sizeof cnt);
  int curl = 0, curr = -1;
  curans = 0;
  for (int i = 0; i < nq; i++) {
    int l = Q[i].l, r = Q[i].r;
    while (curr < r) {
      curr++;
      add(curr);
    }
    while (curr > r) {
      del(curr);
      curr--;
    }
    while (curl < l) {
      del(curl);
      curl++;
    }
    while (curl > l) {
      curl--;
      add(curl);
    }
    ans[Q[i].i] = curans;
  }
  for (int i = 0; i < nq; i++) printf("%d\n", ans[i]);
}
int main() {
  read_file();
  while (scanf("%d%d", &n, &nq) != -1) {
    sqrtn = 0;
    while (sqrtn * sqrtn <= n) sqrtn++;
    sqrtn--;
    mp.clear();
    for (int i = 0; i < n; i++) {
      scanf("%d", &A[i]);
      mp[A[i]];
    }
    int indexer = 0;
    for (it = mp.begin(); it != mp.end(); it++) {
      it->second = indexer;
      rmp[indexer] = it->first;
      indexer++;
    }
    MO();
  }
}
