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;
long long a[100005];
unordered_map<long long, int> mp;
struct query {
  int l, r, index;
};
int block = 320;
struct query b[100005];
int ans[100005];
int currentAns = 0;
void add(int current) {
  mp[a[current]]++;
  if (mp[a[current]] == a[current])
    currentAns++;
  else if (mp[a[current]] == 1 + a[current])
    currentAns--;
}
void remove(int current) {
  mp[a[current]]--;
  if (mp[a[current]] == a[current])
    currentAns++;
  else if (mp[a[current]] == a[current] - 1)
    currentAns--;
}
bool compare(struct query x, struct query y) {
  if (x.l / block != y.l / block) return (x.l < y.l);
  return (x.r < y.r);
}
int main() {
  int n, m, left, right;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%I64d", a + i);
  }
  for (int i = 1; i <= m; ++i) {
    scanf("%d %d", &left, &right);
    b[i].l = left;
    b[i].r = right;
    b[i].index = i;
  }
  sort(b + 1, b + m + 1, compare);
  int currentL = 1;
  int currentR = 1;
  for (int i = 1; i <= m; ++i) {
    int L = b[i].l;
    int R = b[i].r;
    while (currentR <= R) {
      add(currentR);
      currentR++;
    }
    while (currentL > L) {
      add(currentL - 1);
      currentL--;
    }
    while (currentL < L) {
      remove(currentL);
      currentL++;
    }
    while (currentR > R + 1) {
      remove(currentR - 1);
      currentR--;
    }
    ans[b[i].index] = currentAns;
  }
  for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
  return 0;
}
