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;
int nextInt() {
  int x = 0, p = 1;
  char c;
  do {
    c = getchar();
  } while (c <= 32);
  if (c == '-') {
    p = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + (c - '0');
    c = getchar();
  }
  return x * p;
}
const int N = 100500;
const int INF = 1000000000, mod = 1000000000;
const long long LLINF = 1000000000000000000ll;
int BLOCK;
struct query {
  int l, r, idx;
  query() {}
  query(int l, int r, int idx) : l(l), r(r), idx(idx) {}
  bool operator<(const query &other) const {
    int a = l / BLOCK;
    int b = other.l / BLOCK;
    return a < b || (a == b && r < other.r);
  }
};
int answer[N];
int cnt[N];
int a[N];
int n, m;
vector<query> queries;
int curL = 0, curR = -1;
int curAnswer = 0;
int calc(int l, int r) {
  while (curL < l) {
    int x = a[curL];
    if (x <= n) {
      if (cnt[x] == x) curAnswer--;
      cnt[x]--;
      if (cnt[x] == x) curAnswer++;
    }
    curL++;
  }
  while (curR > r) {
    int x = a[curR];
    if (x <= n) {
      if (cnt[x] == x) curAnswer--;
      cnt[x]--;
      if (cnt[x] == x) curAnswer++;
    }
    curR--;
  }
  while (curL > l) {
    --curL;
    int x = a[curL];
    if (x <= n) {
      if (cnt[x] == x) curAnswer--;
      cnt[x]++;
      if (cnt[x] == x) curAnswer++;
    }
  }
  while (curR < r) {
    ++curR;
    int x = a[curR];
    if (x <= n) {
      if (cnt[x] == x) curAnswer--;
      cnt[x]++;
      if (cnt[x] == x) curAnswer++;
    }
  }
  return curAnswer;
}
int main() {
  n = nextInt();
  m = nextInt();
  for (int i = 0; i < n; ++i) {
    a[i] = nextInt();
  }
  queries.resize(m);
  for (int i = 0; i < m; ++i) {
    int l = nextInt() - 1;
    int r = nextInt() - 1;
    queries[i] = query(l, r, i);
  }
  BLOCK = (int)floor(sqrt(n + 0.0));
  sort(queries.begin(), queries.end());
  for (int i = 0; i < m; ++i) {
    answer[queries[i].idx] = calc(queries[i].l, queries[i].r);
  }
  for (int i = 0; i < m; ++i) {
    printf("%d\n", answer[i]);
  }
  return 0;
}
