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;
vector<pair<pair<long long, long long>, long long> > v;
vector<pair<long long, long long> > q;
pair<long long, long long> qr[1000000 + 77];
long long b[1000000 + 77];
long long f[1000000 + 77];
vector<long long> dis;
long long ans[1000000 + 77];
long long a[1000000 + 77];
long long c[1000000 + 77];
map<long long, long long> mp;
map<long long, long long> mm;
int32_t main() {
  long long n, m, l, r;
  scanf("%lld%lld", &n, &m);
  long long val = 0;
  for (long long i = 0; i < n; i++) {
    scanf("%lld", &b[i]);
    if (mp[b[i]] == 0) {
      mp[b[i]] = ++val;
    }
  }
  for (long long i = 0; i < n; i++) {
    a[i] = mp[b[i]];
    c[i] = b[i];
  }
  long long sq = (sqrt(n));
  pair<long long, long long> x, z;
  pair<pair<long long, long long>, long long> y;
  pair<pair<long long, long long>, long long> pii;
  for (long long i = 0; i < m; i++) {
    scanf("%lld%lld", &l, &r);
    l--, r--;
    z = make_pair(l / sq, r);
    x = make_pair(l, r);
    q.push_back(x);
    qr[i] = x;
    y = make_pair(z, i);
    v.push_back(y);
  }
  sort(v.begin(), v.end());
  pii = v[0];
  long long s1 = qr[v[0].second].first;
  long long s2 = qr[v[0].second].second;
  long long res1, res2;
  res1 = 0;
  long long cnt = 0;
  for (long long i = s1; i <= s2; i++) {
    f[a[i]]++;
    if (f[a[i]] == c[i]) cnt++;
    if (f[a[i]] - 1 == c[i]) cnt--;
  }
  ans[v[0].second] = cnt;
  for (long long j = 1; j < v.size(); j++) {
    long long k = v[j].second;
    long long left = qr[k].first, right = qr[k].second;
    if (left < s1) {
      for (long long i = s1 - 1; i >= left; i--) {
        f[a[i]]++;
        if (f[a[i]] == c[i]) cnt++;
        if (f[a[i]] - 1 == c[i]) cnt--;
      }
    } else if (left > s1) {
      for (long long i = s1; i < left; i++) {
        f[a[i]]--;
        if (f[a[i]] == c[i]) {
          cnt++;
        }
        if (f[a[i]] + 1 == c[i]) cnt--;
      }
    }
    if (right > s2) {
      for (long long i = s2 + 1; i <= right; i++) {
        f[a[i]]++;
        if (f[a[i]] == c[i]) cnt++;
        if (f[a[i]] - 1 == c[i]) cnt--;
      }
    } else if (right < s2) {
      for (long long i = s2; i > right; i--) {
        if (f[a[i]] != 0) f[a[i]]--;
        if (f[a[i]] == c[i]) {
          cnt++;
        }
        if (f[a[i]] + 1 == c[i]) cnt--;
      }
    }
    ans[k] = cnt;
    s1 = left, s2 = right;
  }
  for (long long i = 0; i < m; i++) {
    printf("%lld\n", ans[i]);
  }
  return 0;
}
