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 int MAXN = 100000;
class Interval {
 public:
  int s, e, i;
} interval[MAXN + 5];
bool cmp_input(const Interval &a, const Interval &b) { return a.i < b.i; }
bool cmp_interval(const Interval &a, const Interval &b) {
  if (a.s != b.s) return a.s < b.s;
  return a.e < b.e;
}
int arr[MAXN + 5];
int final[MAXN + 5];
int ptr[MAXN + 5];
vector<int> indx[MAXN + 5];
int answer[MAXN + 5];
int freq[MAXN + 5];
int tree[MAXN + 5];
int n, m;
void _update(int ind, int val) {
  for (int i = ind; i <= n; i += i & -i) tree[i] += val;
  return;
}
int _query(int ind) {
  int ret = 0;
  for (int i = ind; i > 0; i -= i & -i) ret += tree[i];
  return ret;
}
void update(int s, int e, int val) {
  _update(s + 1, val);
  _update(e + 2, -val);
  return;
}
int query(int ind) { return _query(ind + 1); }
void preCalculate() {
  int c, c2;
  for (c = 0; c < n; c++) {
    if (c) answer[c] = answer[c - 1];
    if (arr[c] > n) continue;
    freq[arr[c]]++;
    if (freq[arr[c]] == arr[c]) answer[c]++;
    if (freq[arr[c]] == arr[c] + 1) answer[c]--;
    indx[arr[c]].push_back(c);
  }
  for (c = 1; c <= n; c++) indx[c].push_back(n);
  for (c = 0; c < n; c++) update(c, c, answer[c]);
  return;
}
void add(int ind, int from, int val) {
  int to = from + 1;
  if (to >= indx[ind].size()) return;
  update(indx[ind][from], indx[ind][to] - 1, val);
  return;
}
void moveOne(int &start) {
  if (arr[start] > n) {
    start++;
    return;
  }
  add(arr[start], ptr[arr[start]] + arr[start] - 1, -1);
  add(arr[start], ptr[arr[start]] + arr[start], 1);
  ptr[arr[start]]++;
  start++;
  return;
}
int main() {
  FILE *in = stdin;
  int c, c2;
  fscanf(in, "%d%d", &n, &m);
  for (c = 0; c < n; c++) fscanf(in, "%d", &arr[c]);
  for (c = 0; c < m; c++) {
    fscanf(in, "%d%d", &interval[c].s, &interval[c].e);
    interval[c].s--;
    interval[c].e--;
    interval[c].i = c;
  }
  sort(interval, interval + m, cmp_interval);
  preCalculate();
  int start = 0;
  for (c = 0; c < m; c++) {
    while (interval[c].s > start) moveOne(start);
    final[interval[c].i] = query(interval[c].e);
  }
  sort(interval, interval + m, cmp_input);
  for (c = 0; c < m; c++) printf("%d\n", final[c]);
  return 0;
}
