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 int N = 100010;
int a[N];
struct abc {
  int x, y, id;
};
bool cmp(abc a, abc b) { return a.y < b.y || (a.y == b.y && a.x < b.x); }
abc d[N];
map<int, vector<int> > mp;
vector<int> s[N * 4];
void update(int l, int r, int id, int ind, int x) {
  if (l > x) {
    s[id].push_back(x);
    sort(s[id].begin(), s[id].end());
  }
  if (l == r) {
    return;
  }
  int m = (l + r) >> 1;
  if (ind <= m)
    update(l, m, id + id, ind, x);
  else
    update(m + 1, r, id + id + 1, ind, x);
}
void delet(int l, int r, int id, int ind, int x) {
  bool ok = 0;
  for (int i = 0; i < s[id].size(); i++) {
    if (s[id][i] == x) {
      ok = 1;
    }
    if (ok) {
      if (i != s[id].size() - 1)
        s[id][i] = s[id][i + 1];
      else
        s[id].pop_back();
    }
  }
  if (l == r) {
    return;
  }
  int m = (l + r) >> 1;
  if (ind <= m)
    delet(l, m, id + id, ind, x);
  else
    delet(m + 1, r, id + id + 1, ind, x);
}
int sumlr(int l, int r, int id, int ll, int rr) {
  if (ll <= l && r <= rr) {
    vector<int>::iterator it = lower_bound(s[id].begin(), s[id].end(), ll);
    return it - s[id].begin();
  }
  int m = (l + r) >> 1, h = 0;
  if (ll <= m) h += sumlr(l, m, id + id, ll, rr);
  if (rr > m) h += sumlr(m + 1, r, id + id + 1, ll, rr);
  return h;
}
int ans[N];
int main() {
  int n, m, i, j, x, l, r;
  cin >> n >> m;
  for (i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (i = 1; i <= m; i++) {
    scanf("%d %d", &d[i].x, &d[i].y);
    d[i].id = i;
  }
  sort(d + 1, d + m + 1, cmp);
  int id = 1;
  for (i = 1; i <= n; i++) {
    mp[a[i]].push_back(i);
    if (mp[a[i]].size() >= a[i]) {
      int x = 0;
      if (mp[a[i]].size() > a[i]) {
        x = mp[a[i]][mp[a[i]].size() - a[i] - 1];
      }
      update(1, n, 1, mp[a[i]][mp[a[i]].size() - a[i]], x);
      if (mp[a[i]].size() > a[i]) {
        int x = 0;
        if (mp[a[i]].size() > a[i] + 1)
          x = mp[a[i]][mp[a[i]].size() - a[i] - 2];
        delet(1, n, 1, mp[a[i]][mp[a[i]].size() - a[i] - 1], x);
      }
    }
    while (d[id].y == i && id <= m) {
      ans[d[id].id] = sumlr(1, n, 1, d[id].x, d[id].y);
      id++;
    }
  }
  for (i = 1; i <= m; i++) printf("%d\n", ans[i]);
}
