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;
long long int n, a[100005], m, ans = 0, m1[100005], N = 100005;
const long long int block = 600;
bool compare(
    const pair<long long int, pair<long long int, long long int> > &a,
    const pair<long long int, pair<long long int, long long int> > &b) {
  if (a.first / block != b.first / block)
    return a.first / block < b.first / block;
  return a.second.first < b.second.first;
}
long long int fre[100005];
void add(long long int idx) {
  long long int temp = a[idx];
  if (temp > N) return;
  if (fre[temp] == temp) ans--;
  fre[temp]++;
  if (fre[temp] == temp) ans++;
}
void rem(long long int idx) {
  long long int temp = a[idx];
  if (temp > N) return;
  if (fre[temp] == temp) ans--;
  fre[temp]--;
  if (fre[temp] == temp) ans++;
}
int main() {
  long long int i, j, k, p, q, r, l;
  cin >> n >> m;
  for (i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<pair<long long int, pair<long long int, long long int> > > v1;
  for (i = 0; i < m; i++) {
    cin >> p >> q;
    v1.push_back(make_pair(p - 1, make_pair(q - 1, i)));
  }
  sort(v1.begin(), v1.end(), compare);
  l = 0;
  r = 0;
  long long int ans1[100005];
  for (i = 0; i < v1.size(); i++) {
    while (l < v1[i].first) {
      rem(l);
      l++;
    }
    while (l > v1[i].first) {
      l--;
      add(l);
    }
    while (r <= v1[i].second.first) {
      add(r);
      r++;
    }
    while (r > (v1[i].second.first + 1)) {
      rem((r - 1));
      r--;
    }
    ans1[v1[i].second.second] = ans;
  }
  for (i = 0; i < m; i++) {
    cout << ans1[i] << "\n";
  }
  return 0;
}
