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 st {
  int L, R, id;
} query[100005];
int ar[100005], N, block, ans[100005];
int freq[100005];
bool cmp(st q1, st q2) {
  if (q1.L / block == q2.L / block)
    return q1.R < q2.R;
  else
    return q1.L / block < q2.L / block;
}
int main() {
  int i, j, m, currL, currR, cnt, L, R;
  cin >> N >> m;
  for (i = 0; i < N; i++) scanf("%d,", &ar[i]);
  for (i = 0; i < m; i++) {
    scanf("%d,", &query[i].L);
    scanf("%d,", &query[i].R);
    query[i].L--;
    query[i].R--;
    query[i].id = i;
  }
  block = sqrt(N);
  sort(query, query + m, cmp);
  currL = currR = cnt = 0;
  if (ar[currL] <= N) {
    freq[ar[currL]]++;
    if (freq[ar[currL]] == ar[currL]) cnt++;
  }
  for (i = 0; i < m; i++) {
    L = query[i].L;
    R = query[i].R;
    while (currL < L) {
      if (ar[currL] <= N) {
        if (freq[ar[currL]] == ar[currL]) cnt--;
        freq[ar[currL]]--;
        if (freq[ar[currL]] == ar[currL]) cnt++;
      }
      currL++;
    }
    while (currL > L) {
      currL--;
      if (ar[currL] <= N) {
        if (freq[ar[currL]] == ar[currL]) cnt--;
        freq[ar[currL]]++;
        if (freq[ar[currL]] == ar[currL]) cnt++;
      }
    }
    while (currR < R) {
      currR++;
      if (ar[currR] <= N) {
        if (freq[ar[currR]] == ar[currR]) cnt--;
        freq[ar[currR]]++;
        if (freq[ar[currR]] == ar[currR]) cnt++;
      }
    }
    while (currR > R) {
      if (ar[currR] <= N) {
        if (freq[ar[currR]] == ar[currR]) cnt--;
        freq[ar[currR]]--;
        if (freq[ar[currR]] == ar[currR]) cnt++;
      }
      currR--;
    }
    ans[query[i].id] = cnt;
  }
  for (i = 0; i < m; i++) cout << ans[i] << "\n";
  return 0;
}
