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;
struct Query {
  int l, r, stt;
};
const int MAX = 1e5 + 11;
const int lim = 1e5;
int n, m, a[MAX], cn, app[MAX], res[MAX], ans;
Query q[MAX];
bool cmp(Query A, Query B) {
  if (A.l / cn != B.l / cn)
    return A.l / cn < B.l / cn;
  else
    return A.r < B.r;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  cn = sqrt(n);
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1; i <= m; i++) {
    cin >> q[i].l >> q[i].r;
    q[i].stt = i;
  }
  sort(q + 1, q + m + 1, cmp);
  q[0] = {q[1].l, q[1].l - 1, 0};
  for (int i = 1; i <= m; i++) {
    int l1 = q[i - 1].l, r1 = q[i - 1].r;
    int l2 = q[i].l, r2 = q[i].r;
    if (l1 <= l2) {
      for (int j = l1; j <= l2 - 1; j++) {
        if (a[j] > lim) continue;
        if (app[a[j]] == a[j]) ans--;
        app[a[j]]--;
        if (app[a[j]] == a[j]) ans++;
      }
    }
    if (l2 < l1) {
      for (int j = l2; j <= l1 - 1; j++) {
        if (a[j] > lim) continue;
        if (app[a[j]] == a[j]) ans--;
        app[a[j]]++;
        if (app[a[j]] == a[j]) ans++;
      }
    }
    if (r1 <= r2) {
      for (int j = r1 + 1; j <= r2; j++) {
        if (a[j] > lim) continue;
        if (app[a[j]] == a[j]) ans--;
        app[a[j]]++;
        if (app[a[j]] == a[j]) ans++;
      }
    }
    if (r2 < r1) {
      for (int j = r2 + 1; j <= r1; j++) {
        if (a[j] > lim) continue;
        if (app[a[j]] == a[j]) ans--;
        app[a[j]]--;
        if (app[a[j]] == a[j]) ans++;
      }
    }
    res[q[i].stt] = ans;
  }
  for (int i = 1; i <= m; i++) cout << res[i] << "\n";
  return 0;
}
