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 P {
  int l, r, i, res;
  bool operator<(const P& p) const {
    if (r != p.r) return r < p.r;
    return l < p.l;
  }
};
int i, j, k, m, n, l;
int a[100000 + 10], seg[100000 * 4 + 10];
P q[100000 + 10];
vector<int> b[100000 + 10];
bool cmp(P a, P b) { return a.i < b.i; }
void ins(int i, int x, int y, int k, int val) {
  seg[i] += val;
  if (x == y) return;
  int z = (x + y) >> 1;
  if (k <= z)
    ins(i * 2, x, z, k, val);
  else
    ins(i * 2 + 1, z + 1, y, k, val);
}
int query(int i, int x, int y, int l, int r) {
  if (x == l && y == r) return seg[i];
  int z = (x + y) >> 1;
  if (r <= z)
    return query(i * 2, x, z, l, r);
  else if (l > z)
    return query(i * 2 + 1, z + 1, y, l, r);
  else
    return query(i * 2, x, z, l, z) + query(i * 2 + 1, z + 1, y, z + 1, r);
}
int main() {
  while (~scanf("%d%d", &n, &m)) {
    memset(seg, 0, sizeof(seg));
    for (int i = (1); i <= (n); ++i) b[i].clear();
    for (int i = (1); i <= (n); ++i) scanf("%d", &a[i]);
    for (int i = (1); i <= (m); ++i) {
      scanf("%d%d", &q[i].l, &q[i].r);
      q[i].i = i;
    }
    sort(q + 1, q + 1 + m);
    int Idx = 1;
    for (int i = (1); i <= (n); ++i) {
      if (a[i] <= n) {
        k = a[i];
        b[k].push_back(i);
        l = ((int)(b[k]).size());
        if (l >= k) ins(1, 1, n, b[k][l - k], 1);
        if (l > k) ins(1, 1, n, b[k][l - k - 1], -2);
        if (l > k + 1) ins(1, 1, n, b[k][l - k - 2], 1);
      }
      while (Idx <= m && q[Idx].r <= i) {
        q[Idx].res = query(1, 1, n, q[Idx].l, q[Idx].r);
        Idx++;
      }
    }
    sort(q + 1, q + 1 + m, cmp);
    for (int i = (1); i <= (m); ++i) printf("%d\n", q[i].res);
  }
  return 0;
}
