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;
map<int, vector<int> > Z;
const int MXN = 100005 + 15;
int a[MXN];
inline int LB(int x) { return x & (-x); }
struct BIT {
  long long _[MXN];
  int n;
  void init(int m) {
    n = m + 5;
    for (int i = 0; i <= n; i++) _[i] = 0;
  }
  long long query(int w) {
    long long ret = 0;
    for (w += 3; w > 0; w -= LB(w)) ret += _[w];
    return ret;
  }
  void update(int w, long long d) {
    for (w += 3; w < n; w += LB(w)) _[w] += d;
  }
} Y;
int ans[MXN];
int main() {
  if (0)
    freopen(
        ""
        ".in",
        "r", stdin);
  if (0)
    freopen(
        ""
        ".out",
        "w", stdout);
  int i, j, k, _T;
  int n, m;
  while (~scanf("%d%d", &n, &m)) {
    Z.clear();
    for (i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
      Z[a[i]].push_back(i);
    }
    vector<pair<pair<int, int>, int> > TL;
    TL.clear();
    for (i = 1; i <= m; i++) {
      int l, r;
      scanf("%d%d", &l, &r);
      TL.push_back(make_pair(make_pair(r, l), i));
    }
    sort(TL.begin(), TL.end());
    int last = 0;
    Y.init(n + 5);
    for (i = 0; i < TL.size(); i++) {
      int r = TL[i].first.first, l = TL[i].first.second;
      int id = TL[i].second;
      while (last < r) {
        last++;
        int v = a[last];
        k = lower_bound(Z[v].begin(), Z[v].end(), last) - Z[v].begin();
        if (k >= v) {
          Y.update(k > v ? Z[v][k - v - 1] + 1 : 0, -1);
          Y.update(Z[v][k - v] + 1, 1);
        }
      }
      ans[id] = Y.query(l);
    }
    last = 0;
    Y.init(n + 5);
    for (i = 0; i < TL.size(); i++) {
      int r = TL[i].first.first, l = TL[i].first.second;
      int id = TL[i].second;
      while (last < r) {
        last++;
        int v = a[last];
        k = lower_bound(Z[v].begin(), Z[v].end(), last) - Z[v].begin();
        if (k >= v - 1) {
          Y.update(k >= v ? Z[v][k - v] + 1 : 0, -1);
          Y.update(Z[v][k - v + 1] + 1, 1);
        }
      }
      ans[id] -= Y.query(l);
    }
    for (i = 1; i <= m; i++) printf("%d\n", ans[i]);
  }
  return 0;
}
