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>
const long long md = 1e9 + 7;
const int Inf = 1e9;
const long long Inf64 = 1e18;
const long long MaxN = 1e5 + 1;
const long long logN = 20;
const long long MaxM = 11;
const long double eps = 1e-15;
const long long dx[4] = {0, 1, 0, -1};
const long long dy[4] = {1, 0, -1, 0};
const long long ddx[4] = {1, 1, -1, -1};
const long long ddy[4] = {1, -1, 1, -1};
const long double Pi = acos(-1);
using namespace std;
long long gcd(long long a, long long b) {
  while (a) {
    b %= a;
    swap(a, b);
  }
  return b;
}
long long gcdex(long long a, long long mod = md) {
  long long g = mod, r = a, x = 0, y = 1;
  while (r != 0) {
    long long q = g / r;
    g %= r;
    swap(g, r);
    x -= q * y;
    swap(x, y);
  }
  return x < 0 ? x + mod : x;
}
long long binpow(long long a, long long n) {
  long long res = 1;
  while (n) {
    if (n & 1) {
      res *= a;
      res %= md;
    }
    a *= a;
    a %= md;
    n >>= 1;
  }
  return res % md;
}
long long Mp[MaxN];
struct el {
  el() {}
  el(long long a, long long b, long long c) {
    l = a;
    r = b;
    id = c;
  }
  long long l, r;
  long long id;
};
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cerr.tie(0);
  cout << fixed, cout.precision(10);
  long long N, M;
  cin >> N >> M;
  vector<long long> Mt(N);
  for (int i = 0; i < N; i++) {
    cin >> Mt[i];
  }
  vector<long long> Ans(M);
  long long s = sqrt(N) + 1;
  vector<vector<el> > Qr(s);
  for (int i = 0; i < M; i++) {
    long long l, r;
    cin >> l >> r;
    l--;
    r--;
    long long k = l / s;
    Qr[k].push_back({l, r, i + 1});
  }
  for (int i = 0; i < s; i++) {
    sort(Qr[i].begin(), Qr[i].end(), [=](el a, el b) { return a.r < b.r; });
  }
  long long l = 1;
  long long r = 0;
  long long Res = 0;
  for (int i = 0; i < s; i++) {
    for (el a : Qr[i]) {
      while (l > a.l) {
        l--;
        if (Mt[l] <= N) {
          Mp[Mt[l]]++;
          if (Mp[Mt[l]] == Mt[l]) Res++;
          if (Mp[Mt[l]] - 1 == Mt[l]) Res--;
        }
      }
      while (l < a.l) {
        if (Mt[l] <= N) {
          Mp[Mt[l]]--;
          if (Mp[Mt[l]] + 1 == Mt[l]) Res--;
          if (Mp[Mt[l]] == Mt[l]) Res++;
        }
        l++;
      }
      while (r < a.r) {
        r++;
        if (Mt[r] <= N) {
          Mp[Mt[r]]++;
          if (Mp[Mt[r]] == Mt[r]) Res++;
          if (Mp[Mt[r]] - 1 == Mt[r]) Res--;
        }
      }
      while (r > a.r) {
        if (Mt[r] <= N) {
          Mp[Mt[r]]--;
          if (Mp[Mt[r]] + 1 == Mt[r]) Res--;
          if (Mp[Mt[r]] == Mt[r]) Res++;
        }
        r--;
      }
      Ans[a.id - 1] = Res;
    }
  }
  for (long long a : Ans) cout << a << '\n';
  cerr << '\n'
       << "Time execute: " << clock() / (double)CLOCKS_PER_SEC << " sec"
       << '\n';
  return 0;
}
