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, answer, block;
int ans[1000000];
int freq[100005];
int arr[100000 + 5];
struct query {
  int L, R, idx;
};
void add(int x) {
  if (arr[x] > 1e5) return;
  if (freq[arr[x]] == arr[x]) answer--;
  freq[arr[x]]++;
  if (freq[arr[x]] == arr[x]) answer++;
}
void rem(int x) {
  if (arr[x] > 1e5) return;
  if (freq[arr[x]] == arr[x]) answer--;
  freq[arr[x]]--;
  if (freq[arr[x]] == arr[x]) answer++;
}
bool comp(query x, query y) {
  if (x.L / block == y.L / block) return x.R < y.R;
  return x.L / block < y.L / block;
}
int main() {
  int q;
  scanf("%d%d", &n, &q);
  block = ceil(sqrt(n));
  vector<int> v;
  for (int i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
  }
  query Q[q];
  for (int i = 0; i < q; i++)
    scanf("%d%d", &Q[i].L, &Q[i].R), Q[i].idx = i, Q[i].L--, Q[i].R--;
  sort(Q, Q + q, comp);
  int cL = 0, cR = 0;
  for (int i = 0; i < q; i++) {
    int L = Q[i].L, R = Q[i].R;
    while (cL < L) rem(cL), cL++;
    while (cL > L) add(cL - 1), cL--;
    while (cR <= R) add(cR), cR++;
    while (cR > R + 1) rem(cR - 1), cR--;
    ans[Q[i].idx] = answer;
  }
  for (int i = 0; i < q; i++) printf("%d\n", ans[i]);
  return 0;
}
