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 double eps = 1e-9;
const int MAX = 200009;
const int BLK = 555;
int A[MAX];
struct node {
  int L, R, ind;
};
node Q[MAX];
int answ = 0;
int cmpp(node A, node B) {
  if (A.L / BLK == B.L / BLK) return A.R < B.R;
  return A.L / BLK < B.L / BLK;
}
int ha[MAX] = {0};
void add(int ind) {
  if (ha[A[ind]] == A[ind]) {
    answ--;
  }
  ha[A[ind]]++;
  if (ha[A[ind]] == A[ind]) answ++;
}
void remove(int ind) {
  if (ha[A[ind]] == A[ind]) {
    answ--;
  }
  ha[A[ind]]--;
  if (ha[A[ind]] == A[ind]) answ++;
}
int main() {
  int i, j, k;
  int n, q;
  scanf("%d", &n), scanf("%d", &q);
  for (i = 0; i < n; i++) {
    scanf("%d", &A[i]);
    if (A[i] > 1e5) {
      A[i] = 100005;
    }
  }
  for (i = 0; i < q; i++) {
    int l, r;
    scanf("%d", &l), scanf("%d", &r);
    Q[i].L = l - 1;
    Q[i].R = r - 1;
    Q[i].ind = i;
  }
  sort(Q, Q + q, cmpp);
  int cur_l = 0, cur_r = 0;
  int ans[MAX];
  for (int i = 0; i < q; i++) {
    int L = Q[i].L;
    int R = Q[i].R;
    while (cur_l < L) {
      remove(cur_l);
      cur_l++;
    }
    while (cur_r <= R) {
      add(cur_r);
      cur_r++;
    }
    while (cur_l > L) {
      add(cur_l - 1);
      cur_l--;
    }
    while (cur_r > R + 1) {
      remove(cur_r - 1);
      cur_r--;
    }
    ans[Q[i].ind] = answ;
  }
  for (int i = 0; i < q; i++) printf("%d\n", ans[i]);
  return 0;
}
