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;
int ROOT;
int occur[100010];
int results[100010];
struct query {
  int left, right, id;
  query(int l, int r, int id) {
    left = l;
    right = r;
    this->id = id;
  }
  bool operator<(const query& temp) const {
    if ((int)(temp.left - 1) / ROOT == (int)(left - 1) / ROOT)
      return temp.right > right;
    return temp.left > left;
  }
};
std::vector<query> q;
int main() {
  int n, m, u, l, r, i, j, result = 0;
  int moL = 1, moR = 0;
  cin >> n >> m;
  ROOT = (int)ceil(sqrt(n));
  long long* arr;
  arr = new long long[n + 10];
  for (i = 1; i <= n; i++) cin >> arr[i];
  for (i = 0; i < m; i++) {
    cin >> l >> r;
    q.push_back(query(l, r, i + 1));
  }
  sort(q.begin(), q.end());
  for (auto qr : q) {
    l = qr.left;
    r = qr.right;
    while (moR < r) {
      moR++;
      if (arr[moR] < 100010) {
        if (occur[arr[moR]] == arr[moR]) result--;
        occur[arr[moR]]++;
        if (occur[arr[moR]] == arr[moR]) result++;
      }
    }
    while (moR > r) {
      if (arr[moR] < 100010) {
        if (occur[arr[moR]] == arr[moR]) result--;
        occur[arr[moR]]--;
        if (occur[arr[moR]] == arr[moR]) result++;
      }
      moR--;
    }
    while (moL < l) {
      if (arr[moL] < 100010) {
        if (occur[arr[moL]] == arr[moL]) result--;
        occur[arr[moL]]--;
        if (occur[arr[moL]] == arr[moL]) result++;
      }
      moL++;
    }
    while (moL > l) {
      moL--;
      if (arr[moL] < 100010) {
        if (occur[arr[moL]] == arr[moL]) result--;
        occur[arr[moL]]++;
        if (occur[arr[moL]] == arr[moL]) result++;
      }
    }
    results[qr.id] = result;
  }
  for (int i = 1; i <= m; i++) cout << results[i] << endl;
}
