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;
using ll = long long;
using ull = unsigned long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
const int sz = 100010;
struct Function {
  ll To_int(string str) {
    stringstream ss(str);
    ll x = 0;
    ss >> x;
    return x;
  }
  string To_string(ll x) {
    stringstream ss;
    ss << x;
    string str = ss.str();
    return str;
  }
  bool vowel_up(char c) {
    return c == 'A' || c == 'E' || c == 'I' || c == 'U' || c == 'O' || c == 'Y';
  }
  bool vowel_low(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'u' || c == 'o' || c == 'y';
  }
  template <typename T>
  T gcd(T a, T b) {
    if (a < 0) return gcd(-a, b);
    if (b < 0) return gcd(a, -b);
    return (b == 0) ? a : gcd(b, a % b);
  }
  template <typename T>
  T lcm(T a, T b) {
    if (a < 0) return lcm(-a, b);
    if (b < 0) return lcm(a, -b);
    return a * (b / gcd(a, b));
  }
};
void inout() {}
const int block = 316;
struct query {
  int l, r, ind;
};
vector<query> Q;
vector<int> ans;
vector<int> ara;
unordered_map<int, int> freq;
int cnt = 0;
void add(int index) {
  freq[ara[index]]++;
  if (freq[ara[index]] == ara[index]) cnt++;
  if (freq[ara[index]] == ara[index] + 1) cnt--;
}
void remove(int index) {
  freq[ara[index]]--;
  if (freq[ara[index]] == ara[index]) cnt++;
  if (freq[ara[index]] == ara[index] - 1) cnt--;
}
bool cmp(query f, query s) {
  if ((f.l / block) != (s.l / block))
    return (f.l / block) < (s.l / block);
  else
    return f.r < s.r;
}
void MOS_ALGO(int q) {
  int ML = 0, MR = -1;
  sort((Q).begin(), (Q).end(), cmp);
  for (int i = 0; i < q; i++) {
    int left = Q[i].l, right = Q[i].r;
    while (MR < right) {
      MR++;
      add(MR);
    }
    while (ML > left) {
      ML--;
      add(ML);
    }
    while (MR > right) {
      remove(MR);
      MR--;
    }
    while (ML < left) {
      remove(ML);
      ML++;
    }
    ans[Q[i].ind] = cnt;
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, q;
  cin >> n >> q;
  ara.resize(n);
  Q.resize(q);
  ans.resize(q);
  for (auto &i : ara) cin >> i;
  for (int i = 0; i < q; i++) {
    cin >> Q[i].l >> Q[i].r;
    Q[i].ind = i;
    Q[i].l--;
    Q[i].r--;
  }
  MOS_ALGO(q);
  for (auto i : ans) cout << i << "\n";
  return 0;
}
