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>
const int N = 1e6 + 30;
std::vector<int> v[N];
int n, m;
int a[N], ans[N], pos[N], s[N], b[N];
struct NODE {
  int l, r, id;
} q[N];
struct SEGMENTTREE {
  int l, r, s;
} t[N << 2];
int read() {
  int s = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch >= '0' && ch <= '9')
    s = (s << 3) + (s << 1) + ch - '0', ch = getchar();
  return s;
}
int cmp(NODE x, NODE y) { return x.r < y.r; }
void build(int p, int l, int r) {
  t[p].l = l, t[p].r = r;
  if (t[p].l == t[p].r) return;
  int mid = l + r >> 1;
  build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
}
void change(int p, int pos, int val) {
  if (t[p].l == t[p].r) {
    t[p].s = val;
    return;
  }
  int mid = t[p].l + t[p].r >> 1;
  if (pos <= mid)
    change(p << 1, pos, val);
  else
    change(p << 1 | 1, pos, val);
  t[p].s = t[p << 1].s + t[p << 1 | 1].s;
}
int ask(int p, int l, int r) {
  if (t[p].l >= l && t[p].r <= r) return t[p].s;
  int mid = t[p].l + t[p].r >> 1, tot = 0;
  if (l <= mid) tot += ask(p << 1, l, r);
  if (mid < r) tot += ask(p << 1 | 1, l, r);
  return tot;
}
int main() {
  n = read(), m = read();
  for (int i = 1; i <= n; ++i) s[i] = read(), b[i] = s[i];
  std::sort(s + 1, s + n + 1);
  int len = std::unique(s + 1, s + n + 1) - s - 1;
  for (int i = 1; i <= n; ++i)
    a[i] = std::lower_bound(s + 1, s + len + 1, b[i]) - s;
  for (int i = 1; i <= n; ++i)
    v[a[i]].push_back(i), pos[i] = v[a[i]].size() - 1;
  for (int i = 1; i <= m; ++i) q[i].l = read(), q[i].r = read(), q[i].id = i;
  std::sort(q + 1, q + m + 1, cmp);
  build(1, 1, n);
  for (int i = 1; i <= m; ++i) {
    int last = q[i - 1].r + 1;
    for (int j = last; j <= q[i].r; ++j) {
      if (pos[j] - b[j] + 1 >= 0) {
        if (pos[j] - b[j] >= 0) change(1, v[a[j]][pos[j] - b[j]], -1);
        if (pos[j] - b[j] - 1 >= 0) change(1, v[a[j]][pos[j] - b[j] - 1], 0);
        change(1, v[a[j]][pos[j] - b[j] + 1], 1);
      }
    }
    ans[q[i].id] = ask(1, q[i].l, q[i].r);
  }
  for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
  return 0;
}
