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>
inline int sbt(int x) { return __builtin_popcount(x); }
using namespace std;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
vector<pair<int, pair<int, int>>> queries;
int a[100013];
int block_sz = 317;
int n, q, l, r;
vector<int> ans;
int freq[100013];
int block_a, block_b, quer_ans;
bool cmp(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
  block_a = (a.first) / block_sz;
  block_b = (b.first) / block_sz;
  if (block_a != block_b) {
    return block_a < block_b;
  }
  return a.second.first < b.second.first;
}
void rem(int x) {
  if (x > n) return;
  freq[x]--;
  if (freq[x] == x) {
    quer_ans++;
  } else if (freq[x] == (x - 1)) {
    quer_ans--;
  }
}
void add(int x) {
  if (x > n) return;
  freq[x]++;
  if (freq[x] == (x + 1))
    quer_ans--;
  else if (freq[x] == x)
    quer_ans++;
}
int main() {
  cin.sync_with_stdio(false);
  cout.sync_with_stdio(false);
  cin >> n >> q;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < q; i++) {
    cin >> l >> r;
    queries.push_back(make_pair(l - 1, make_pair(r - 1, i)));
  }
  ans.resize(q);
  sort(queries.begin(), queries.end(), cmp);
  int mo_rgt = -1, mo_lft = 0;
  for (auto query : queries) {
    l = query.first;
    r = query.second.first;
    while (mo_rgt < r) {
      mo_rgt++;
      add(a[mo_rgt]);
    }
    while (mo_rgt > r) {
      rem(a[mo_rgt]);
      mo_rgt--;
    }
    while (mo_lft > l) {
      mo_lft--;
      add(a[mo_lft]);
    }
    while (mo_lft < l) {
      rem(a[mo_lft]);
      mo_lft++;
    }
    ans[query.second.second] = quer_ans;
  }
  for (auto res : ans) cout << res << endl;
  return 0;
}
