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;
bool isprime(long long x) {
  for (long long i = 2; i * i <= x; i++)
    if (x % i == 0) return 0;
  return 1;
}
const double pi = acos(-1);
int block, n, m, res[100000 + 5], T[100000 + 5], l, r, LEFT, RIGHT, ans;
unordered_map<int, int> cnt;
struct Query {
  int L, R, pos;
} q[100000 + 5];
bool Mo(Query x, Query y) {
  if (x.L / block != y.L / block) return x.L / block < y.L / block;
  return x.R < y.R;
}
void addLEFT() {
  while (l < LEFT) {
    LEFT--;
    cnt[T[LEFT]]++;
    if (cnt[T[LEFT]] == T[LEFT])
      ans++;
    else if (cnt[T[LEFT]] == T[LEFT] + 1)
      ans--;
  }
}
void addRIGHT() {
  while (r > RIGHT) {
    RIGHT++;
    cnt[T[RIGHT]]++;
    if (cnt[T[RIGHT]] == T[RIGHT])
      ans++;
    else if (cnt[T[RIGHT]] == T[RIGHT] + 1)
      ans--;
  }
}
void removeLEFT() {
  while (LEFT < l) {
    cnt[T[LEFT]]--;
    if (cnt[T[LEFT]] == T[LEFT])
      ans++;
    else if (cnt[T[LEFT]] == T[LEFT] - 1)
      ans--;
    LEFT++;
  }
}
void removeRIGHT() {
  while (RIGHT > r) {
    cnt[T[RIGHT]]--;
    if (cnt[T[RIGHT]] == T[RIGHT])
      ans++;
    else if (cnt[T[RIGHT]] == T[RIGHT] - 1)
      ans--;
    RIGHT--;
  }
}
void readTable() {
  for (int i = 0; i < n; i++) cin >> T[i];
}
void readQueries() {
  for (int i = 0; i < m; i++)
    cin >> q[i].L >> q[i].R, q[i].L--, q[i].R--, q[i].pos = i;
}
void outputResult() {
  for (int i = 0; i < m; i++) cout << res[i] << '\n';
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  block = sqrt(n);
  readTable();
  readQueries();
  sort(q, q + m, Mo);
  LEFT = q[0].L, RIGHT = LEFT;
  cnt[T[LEFT]]++;
  if (T[LEFT] == 1) ans++;
  for (int i = 0; i < m; i++) {
    l = q[i].L, r = q[i].R;
    addLEFT();
    removeLEFT();
    addRIGHT();
    removeRIGHT();
    res[q[i].pos] = ans;
  }
  outputResult();
  return 0;
}
