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>
struct query {
  int32_t l, r, i;
};
using namespace std;
int32_t didelis[100005];
int32_t total = 0;
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  fill(didelis, didelis + 100005, 0);
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int32_t n, q;
  cin >> n >> q;
  const int32_t sqrtn = 320;
  int32_t a[n];
  query u[q];
  for (int32_t i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int32_t i = 0; i < q; i++) {
    cin >> u[i].l >> u[i].r;
    u[i].l--;
    u[i].i = i;
  }
  sort(u, u + q, [&](query &i, query &j) {
    if (i.l / sqrtn == j.l / sqrtn) return i.r < j.r;
    return i.l / sqrtn < j.l / sqrtn;
  });
  auto pridet = [&](int32_t x) {
    if (x > 100000) return;
    if (didelis[x] == x) total--;
    didelis[x]++;
    if (didelis[x] == x) total++;
  };
  auto atimt = [&](int32_t x) {
    if (x > 100000) return;
    if (didelis[x] == x) total--;
    didelis[x]--;
    if (didelis[x] == x) total++;
  };
  int32_t pr = 0, pab = 0;
  int32_t ats[q];
  for (query &t : u) {
    while (pr > t.l) {
      pr--;
      pridet(a[pr]);
    }
    while (pr < t.l) {
      atimt(a[pr]);
      pr++;
    }
    while (pab > t.r) {
      pab--;
      atimt(a[pab]);
    }
    while (pab < t.r) {
      pridet(a[pab]);
      pab++;
    }
    ats[t.i] = total;
  }
  for (int32_t i = 0; i < q; i++) {
    cout << ats[i] << "\n";
  }
}
