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;
int N, M, A[100005], f[100005], nposs, poss_num[455];
int sums[455][100005];
char appear[455][100005];
void Test() {
  int i;
  printf("Array :\n");
  for (i = 1; i <= N; ++i) {
    printf("%d\n", A[i]);
  }
  printf("%d possible numbers :\n", nposs);
  for (i = 1; i <= nposs; ++i) {
    printf("%d\n", poss_num[i]);
  }
  for (i = 1; i <= N; ++i) {
    printf("Frequency of %d is %d\n", A[i], f[A[i]]);
  }
}
void Read() {
  int i;
  scanf("%d %d", &N, &M);
  for (i = 1; i <= N; ++i) {
    scanf("%d", &A[i]);
  }
}
void Frequencies() {
  int i;
  for (i = 1; i <= N; ++i) {
    if (A[i] <= N) {
      ++f[A[i]];
    }
  }
}
void Possible_Nums() {
  int i;
  for (i = 1; i <= N; ++i) {
    if (f[i] >= i) {
      poss_num[++nposs] = i;
    }
  }
}
int Position(int x) {
  int lo, mid, hi;
  lo = 1;
  hi = nposs;
  while (lo < hi) {
    mid = (lo + hi + 1) / 2;
    if (poss_num[mid] <= x) {
      lo = mid;
    } else {
      hi = mid - 1;
    }
  }
  return lo;
}
void Appear() {
  int i, pos;
  for (i = 1; i <= N; ++i) {
    if (A[i] <= N && f[A[i]] >= A[i]) {
      pos = Position(A[i]);
      appear[pos][i] = 1;
    }
  }
}
void Make_Sums() {
  int i, j;
  for (i = 1; i <= nposs; ++i) {
    for (j = 1; j <= N; ++j) {
      sums[i][j] = sums[i][j - 1] + appear[i][j];
    }
  }
}
void Answer_Queries() {
  int i, from, to, ans, possible;
  for (i = 1; i <= M; ++i) {
    scanf("%d %d", &from, &to);
    ans = 0;
    for (possible = 1; possible <= nposs; ++possible) {
      if (sums[possible][to] - sums[possible][from - 1] == poss_num[possible]) {
        ++ans;
      }
    }
    printf("%d\n", ans);
  }
}
int main(void) {
  Read();
  Frequencies();
  Possible_Nums();
  Appear();
  Make_Sums();
  Answer_Queries();
  return (0);
}
