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;
const int oo = 0x3f3f3f3f;
const double eps = 1e-9;
int inext_[100100];
int mnext_[100100];
int last[100100];
int nums[100100], N, Q;
int interesting[1024], I;
bool numDone[100100];
int BIT[123456];
void update(int n, int v) {
  for (; n < 123456; n += n & -n) BIT[n] += v;
}
int query(int n) {
  int res = 0;
  for (; n; n -= n & -n) res += BIT[n];
  return res;
}
int res[100100];
pair<pair<int, int>, int> queries[100100];
int main() {
  memset(last, -1, sizeof(last));
  memset(inext_, -1, sizeof(inext_));
  memset(mnext_, -1, sizeof(mnext_));
  cin >> N >> Q;
  for (int i = (0); i < (N); i++) cin >> nums[i];
  for (int i = (0); i < (N); i++) {
    if (nums[i] <= N) {
      if (last[nums[i]] != -1) {
        inext_[last[nums[i]]] = i;
      }
      last[nums[i]] = i;
    }
  }
  memset(numDone, 0, sizeof(numDone));
  for (int i = (0); i < (N); i++) {
    if (N - i < nums[i]) continue;
    if (numDone[nums[i]]) continue;
    numDone[nums[i]] = true;
    int cid = i;
    for (int j = (1); j < (nums[i]); j++) {
      cid = inext_[cid];
      if (cid == -1) break;
    }
    if (cid == -1) continue;
    interesting[I++] = nums[i];
    int lid = i;
    while (cid != -1) {
      mnext_[lid] = cid;
      lid = inext_[lid];
      cid = inext_[cid];
    }
  }
  for (int i = (0); i < (Q); i++) {
    cin >> queries[i].first.first >> queries[i].first.second;
    queries[i].second = i;
  }
  sort(queries, queries + Q);
  int C = N;
  for (int q = int(Q) - 1; q >= (0); q--) {
    int from = queries[q].first.first;
    int to = queries[q].first.second;
    int qid = queries[q].second;
    while (C >= from) {
      if (nums[--C] <= N) {
        int id = mnext_[C];
        if (id == -1) continue;
        update(id + 1, 1);
        id = inext_[id];
        if (id == -1) continue;
        update(id + 1, -2);
        id = inext_[id];
        if (id == -1) continue;
        update(id + 1, 1);
      }
    }
    res[qid] = query(to);
  }
  for (int q = (0); q < (Q); q++) cout << res[q] << endl;
  return 0;
}
