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 N = 1e5 + 7;
const long long int MOD = 1e9;
const long long int INF = 1e9 + 5;
struct node {
  int ans = 0, l, r, i;
};
int n, m;
node seg[4 * N];
node merge(node a, node b) {
  node c;
  c.ans = a.ans + b.ans;
  return c;
}
void build(int idx = 1, int l = 0, int r = n) {
  if (r - l < 2) {
    seg[idx].ans = 0;
    return;
  }
  int mid = (l + r) >> 1;
  build(idx << 1, l, mid);
  build(idx << 1 | 1, mid, r);
  seg[idx] = merge(seg[idx << 1], seg[idx << 1 | 1]);
}
void modify(int pos, int val, int idx = 1, int l = 0, int r = n) {
  if (r - l < 2) {
    seg[idx].ans += val;
    return;
  }
  int mid = (l + r) >> 1;
  if (pos < mid)
    modify(pos, val, idx << 1, l, mid);
  else
    modify(pos, val, idx << 1 | 1, mid, r);
  seg[idx] = merge(seg[idx << 1], seg[idx << 1 | 1]);
}
node query(int ql, int qr, int idx = 1, int l = 0, int r = n) {
  if (qr <= l || r <= ql) {
    node I;
    I.ans = 0;
    return I;
  }
  if (ql <= l && r <= qr) return seg[idx];
  int mid = (l + r) >> 1;
  return merge(query(ql, qr, idx << 1, l, mid),
               query(ql, qr, idx << 1 | 1, mid, r));
}
bool comp(node a, node b) {
  if (a.r == b.r) return a.l < b.l;
  return a.r < b.r;
}
void pre() {}
void solve(long long int kk) {
  cin >> n >> m;
  vector<int> a(n, 0), ans(m, 0);
  map<int, vector<int> > v;
  vector<node> queries;
  build();
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (a[i] > 1e5) a[i] = 0;
  }
  for (int i = 0; i < m; i++) {
    node nn;
    nn.i = i;
    cin >> nn.l >> nn.r;
    nn.l--;
    nn.r--;
    queries.push_back(nn);
  }
  sort(queries.begin(), queries.end(), comp);
  int idx = 0;
  for (int R = 0; R < n; R++) {
    if (!a[R]) continue;
    v[a[R]].push_back(R);
    int P = v[a[R]].size();
    if (P >= a[R]) {
      modify(v[a[R]][P - a[R]], +1);
    }
    if (P >= a[R] + 1) {
      modify(v[a[R]][P - a[R] - 1], -2);
    }
    if (P >= a[R] + 2) {
      modify(v[a[R]][P - a[R] - 2], +1);
    }
    while (idx < m && queries[idx].r == R) {
      ans[queries[idx].i] = query(queries[idx].l, queries[idx].r + 1).ans;
      idx++;
    }
  }
  for (int i = 0; i < m; i++) cout << ans[i] << "\n";
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int t = 1;
  pre();
  for (long long int kk = 1; kk <= t; kk++) {
    solve(kk);
  }
}
