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>
#pragma GCC optimize("Ofast")
using namespace std;
template <typename T, typename TT>
inline ostream &operator<<(ostream &os, const pair<T, TT> &t) {
  return os << t.first << " " << t.second;
}
template <typename T>
inline ostream &operator<<(ostream &os, const vector<T> &t) {
  for (auto i : t) os << i << " ";
  return os;
}
template <typename T>
inline ostream &operator<<(ostream &os, const set<T> &t) {
  for (auto i : t) os << i << " ";
  return os;
}
template <typename T1, typename T2>
inline ostream &operator<<(ostream &os, const map<T1, T2> &t) {
  for (auto i : t) os << i.first << " : " << i.second << '\n';
  return os;
}
template <typename T>
inline istream &operator>>(istream &is, vector<T> &v) {
  for (T &t : v) is >> t;
  return is;
}
template <typename T1, typename T2>
inline istream &operator>>(istream &is, vector<pair<T1, T2>> &v) {
  for (pair<T1, T2> &t : v) is >> t.first >> t.second;
  return is;
}
const long long mod = 1e9 + 7;
template <class T>
struct fenwick_tree {
 public:
  fenwick_tree() : _n(0) {}
  fenwick_tree(int n) : _n(n), data(n) {}
  void add(int p, T x) {
    assert(0 <= p && p < _n);
    p++;
    while (p <= _n) {
      data[p - 1] += T(x);
      p += p & -p;
    }
  }
  T sum(int l, int r) {
    assert(0 <= l && l <= r && r <= _n);
    return sum(r) - sum(l);
  }

 private:
  int _n;
  std::vector<T> data;
  T sum(int r) {
    T s = 0;
    while (r > 0) {
      s += data[r - 1];
      r -= r & -r;
    }
    return s;
  }
};
void solve() {
  long long n, m;
  cin >> n >> m;
  vector<long long> v(n);
  cin >> v;
  fenwick_tree<long long> fen(n + 2);
  map<long long, vector<long long>> ls;
  vector<vector<long long>> q(m, vector<long long>(3));
  for (int i = 0; i < m; i++) {
    cin >> q[i][0] >> q[i][1];
    q[i][2] = i;
  }
  sort(q.begin(), q.end(),
       [&](const vector<long long> &a, const vector<long long> &b) -> bool {
         return a[1] < b[1];
       });
  vector<long long> ans(m);
  int j = 0;
  for (int i = 1; i <= n; i++) {
    vector<long long> &cur = ls[v[i - 1]];
    long long e = v[i - 1];
    cur.push_back(i);
    if (cur.size() >= e) {
      fen.add(cur[cur.size() - e], 1);
      if (cur.size() > e) fen.add(cur[cur.size() - e - 1], -2);
      if (cur.size() > e + 1) fen.add(cur[cur.size() - e - 2], 1);
    }
    while (j < m and q[j][1] <= i) {
      ans[q[j][2]] = fen.sum(q[j][0], q[j][1] + 1);
      j++;
    }
  }
  for (int i = 0; i < m; i++) cout << ans[i] << '\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  long long T = 1;
  while (T--) {
    solve();
  }
  return 0;
}
