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 ii = pair<int, int>;
struct SegmentTree {
 private:
  vector<ll> s, up;
  vector<int> l, r;
  int n, k, start;
  int ql, qr, qv;
  inline bool in_range(int z) { return (ql <= l[z] && r[z] <= qr); }
  inline bool out_range(int z) { return (ql > r[z] || qr < l[z]); }
  ll combine(ll a, ll b) { return a + b; }
  void pull(int z) { s[z] = combine(s[2 * z], s[2 * z + 1]); }
  void push(int z) {
    ll t = up[z];
    up[z] = 0;
    s[z] += (r[z] - l[z] + 1) * t;
    if (z >= start) return;
    up[2 * z] += t;
    up[2 * z + 1] += t;
  }
  void build() {
    for (int i = start - 1; i >= 1; i--) {
      pull(i);
      l[i] = l[2 * i];
      r[i] = r[2 * i + 1];
    }
  }
  ll query(int z) {
    push(z);
    if (in_range(z)) return s[z];
    if (out_range(z)) return 0;
    return combine(query(2 * z), query(2 * z + 1));
  }
  void update(int z) {
    push(z);
    if (in_range(z)) {
      up[z] += qv;
      push(z);
      return;
    }
    if (out_range(z)) return;
    update(2 * z);
    update(2 * z + 1);
    pull(z);
  }

 public:
  SegmentTree(int _n) {
    n = _n;
    k = 0;
    while ((1 << k) < n) k++;
    start = (1 << k);
    s.assign(2 * start, 0);
    up.assign(2 * start, 0);
    l.assign(2 * start, 0);
    r.assign(2 * start, 0);
    for (int i = 0; i < start; i++) {
      l[start + i] = r[start + i] = i;
    }
    build();
  }
  ll query(int lf, int rt) {
    ql = lf;
    qr = rt;
    return query(1);
  }
  void update(int lf, int rt, int val) {
    ql = lf;
    qr = rt;
    qv = val;
    update(1);
  }
};
const int N = 1e5 + 666;
vector<ii> qry[N];
vector<int> pos[N];
int a[N], ans[N], id[N], n, m;
void solve() {
  SegmentTree st(n + 1);
  for (int i = 1; i <= n; i++) {
    if (id[i] >= a[i]) {
      vector<int>& p = pos[a[i]];
      int z = id[i] - a[i];
      if (z >= 0) st.update(p[z] + 1, p[z + 1], 1);
      if (z > 0) st.update(p[z - 1] + 1, p[z], -1);
    }
    for (ii t : qry[i]) {
      ans[t.second] = st.query(t.first, t.first);
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= n; i++) pos[i].push_back(0);
  for (int i = 1; i <= n; i++) {
    if (a[i] >= N) a[i] = N - 1;
    id[i] = (int)(pos[a[i]]).size();
    pos[a[i]].push_back(i);
  }
  int l, r;
  for (int i = 0; i < m; i++) {
    cin >> l >> r;
    qry[r].push_back({l, i});
  }
  solve();
  for (int i = 0; i < m; i++) cout << ans[i] << '\n';
}
