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 long long INF = 1e18 + 7;
const long long maxn = 2e5 + 700;
const int M = 1e6 + 8;
const long long mod = 1e6 + 7;
const double eps = 1e-9;
const double PI = acos(-1);
auto random_address = [] {
  char *p = new char;
  delete p;
  return uint64_t(p);
};
const uint64_t SEED = chrono::steady_clock::now().time_since_epoch().count() *
                      (random_address() | 1);
mt19937_64 rng(SEED);
template <typename T>
inline void read(T &a) {
  char c = getchar();
  T x = 0, f = 1;
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + c - '0';
    c = getchar();
  }
  a = f * x;
}
long long n, m, p;
long long a[maxn], sum[maxn];
void add(int pos, int val) {
  while (pos <= n) {
    sum[pos] += val;
    pos += pos & -pos;
  }
}
long long query(int pos) {
  long long ans = 0;
  while (pos) {
    ans += sum[pos];
    pos -= pos & -pos;
  }
  return ans;
}
vector<pair<int, int>> q[maxn];
long long res[maxn];
multiset<int> s[maxn];
int main() {
  read(n);
  read(m);
  for (int i = 1; i <= n; i++) read(a[i]);
  for (int i = 1; i <= m; i++) {
    int x, y;
    read(x);
    read(y);
    if (x > y) swap(x, y);
    q[y].push_back({x, i});
  }
  for (int i = 1; i <= n; i++) {
    if (a[i] <= n) {
      s[a[i]].insert(i);
      int sz = s[a[i]].size();
      if (sz == a[i] + 1) {
        int sp = *s[a[i]].begin(), tp = *next(s[a[i]].begin());
        int temp = query(sp) - query(sp - 1);
        add(sp, -2);
        add(tp, 1);
      } else if (sz == a[i]) {
        int sp = *s[a[i]].begin();
        add(sp, 1);
      } else if (sz == a[i] + 2) {
        int sp = *s[a[i]].begin(), tp = *next(s[a[i]].begin()),
            tpp = *next(next(s[a[i]].begin()));
        int temp = query(sp) - query(sp - 1);
        int tempx = query(tp) - query(tp - 1);
        add(sp, 1);
        add(tp, -2);
        add(tpp, 1);
        s[a[i]].erase(sp);
      }
    }
    for (auto x : q[i]) res[x.second] = query(i) - query(x.first - 1);
  }
  for (int i = 1; i <= m; i++) {
    printf("%lld\n", res[i]);
  }
  return 0;
}
