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 long long int M = 1000000007;
long long int power(long long int x, long long int n, long long int m) {
  if (n == 0)
    return 1;
  else if (n % 2 == 0)
    return (power(((x % m) * (x % m)) % m, n / 2, m)) % m;
  else
    return ((x % m) * power(x, n - 1, m) % m);
}
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
long long int ncr(int n, int r) {
  if (r > n) return 0;
  if (r > n - r) r = n - r;
  long long int ans = 1;
  int i;
  for (i = 1; i <= r; i++) {
    ans *= n - r + i;
    ans /= i;
  }
  return ans;
}
map<long long int, pair<long long int, long long int>> mp;
map<pair<long long int, long long int>, long long int> pr;
vector<pair<long long int, long long int>> vec;
long long int num[100001];
unordered_map<long long int, long long int> freq;
long long int d = sqrtl(100001);
long long int cmp(pair<long long int, long long int> p1,
                  pair<long long int, long long int> p2) {
  long long int l1 = p1.first / d;
  long long int l2 = p2.first / d;
  long long int r1 = p1.second / d;
  long long int r2 = p2.second / d;
  if (l2 > l1) return 1;
  if (l1 == l2 && r2 > r1) return 1;
  return 0;
}
long long int ans = 0, ml = 0, mr = -1;
void find_distict(long long int l, long long int r) {
  for (long long int i = ml; i < l; i++) {
    freq[num[i]] -= 1;
    if (freq[num[i]] == num[i])
      ans += 1;
    else {
      if (freq[num[i]] + 1 == num[i]) ans -= 1;
    }
  }
  for (long long int i = ml - 1; i >= l; i--) {
    freq[num[i]] += 1;
    if (freq[num[i]] == num[i])
      ans += 1;
    else {
      if (freq[num[i]] - 1 == num[i]) ans -= 1;
    }
  }
  for (long long int i = mr + 1; i <= r; i++) {
    freq[num[i]] += 1;
    if (freq[num[i]] == num[i])
      ans += 1;
    else {
      if (freq[num[i]] - 1 == num[i]) ans -= 1;
    }
  }
  for (long long int i = mr; i > r; i--) {
    freq[num[i]] -= 1;
    if (freq[num[i]] == num[i])
      ans += 1;
    else {
      if (freq[num[i]] + 1 == num[i]) ans -= 1;
    }
  }
  pr[{l, r}] = ans;
  ml = l, mr = r;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL), cout.tie(NULL);
  long long int n, q, l, r;
  cin >> n >> q;
  for (int i = 0; i < n; i++) {
    cin >> num[i];
  }
  for (int i = 0; i < q; i++) {
    cin >> l >> r;
    l -= 1, r -= 1;
    mp[i] = {l, r};
    vec.push_back({l, r});
  }
  sort(vec.begin(), vec.end(), cmp);
  for (int i = 0; i < vec.size(); i++) {
    find_distict(vec[i].first, vec[i].second);
  }
  for (int i = 0; i < q; i++) {
    cout << pr[mp[i]] << "\n";
  }
  return 0;
}
