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;
template <typename T>
inline T Abs(T x) {
  return (x >= 0) ? x : -x;
}
template <typename T>
inline T sqr(T x) {
  return x * x;
}
const int INF = (int)1E9;
const long long INF64 = (long long)1E18;
const long double EPS = 1E-9;
const long double PI = 3.1415926535897932384626433832795;
const int MAXN = 100100;
const int OSN = (1 << 17) - 1;
int tree[2 * OSN + 100];
int n, m, a[MAXN], l[MAXN], r[MAXN], ans[MAXN];
vector<pair<int, int> > q[MAXN];
vector<int> v[MAXN];
int get(int v, int l, int r, int x) {
  if (l <= x && x <= r) {
    int res = tree[v];
    if (l != r) {
      int mid = (l + r) >> 1;
      res += get(2 * v, l, mid, x);
      res += get(2 * v + 1, mid + 1, r, x);
    }
    return res;
  } else
    return 0;
}
void update(int v, int l, int r, int ll, int rr, int value) {
  if (l > rr || ll > r || ll > rr) return;
  if (ll <= l && r <= rr) {
    tree[v] += value;
    return;
  }
  int mid = (l + r) >> 1;
  update(2 * v, l, mid, ll, rr, value);
  update(2 * v + 1, mid + 1, r, ll, rr, value);
}
void recalc(int num, int l, int value) {
  if (num > n) return;
  vector<int> &a = v[num];
  int la = (int)(lower_bound((a).begin(), (a).end(), l) - a.begin());
  if (la == (int)a.size()) return;
  int ra = la + num - 1;
  if (ra >= (int)a.size()) return;
  if (ra + 1 == (int)a.size())
    update(1, 1, OSN, a[ra], n, value);
  else
    update(1, 1, OSN, a[ra], a[ra + 1] - 1, value);
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < (int)(n); i++) {
    scanf("%d", &a[i]);
    if (a[i] <= n) v[a[i]].push_back(i + 1);
  }
  for (int i = 0; i < (int)(m); i++) {
    scanf("%d%d", &l[i], &r[i]);
    q[l[i]].push_back(make_pair(r[i], i));
  }
  for (int i = 0; i < (int)(n); i++) {
    if (i == 0)
      for (int value = 0; value < (int)(MAXN); value++) recalc(value, 1, +1);
    for (int j = 0; j < (int)(q[i + 1].size()); j++) {
      int r = q[i + 1][j].first, id = q[i + 1][j].second;
      ans[id] = get(1, 1, OSN, r);
    }
    recalc(a[i], i + 1, -1);
    recalc(a[i], i + 2, +1);
  }
  for (int i = 0; i < (int)(m); i++) printf("%d\n", ans[i]);
  return 0;
}
