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 = 1e6 + 10;
struct _Query {
  long long l, r, id;
} query[MAXN];
long long belong[MAXN];
bool cmp1(_Query a, _Query b) {
  return belong[a.l] ^ belong[b.l] ? belong[a.l] < belong[b.l]
         : belong[a.l] & 1         ? a.r < b.r
                                   : a.r > b.r;
}
long long n, m, cnt, num[MAXN], tot;
long long ans[MAXN], col[MAXN];
long long head = 1, tail = 0;
long long read() {
  long long res = 0;
  char c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar();
  return res;
}
void printi(long long x) {
  if (x / 10) printi(x / 10);
  putchar(x % 10 + '0');
}
void move(long long st, long long ed) {
  while (head < st) {
    if (col[head] <= n) {
      if (num[col[head]] == col[head]) tot--;
      num[col[head]]--;
      if (num[col[head]] == col[head]) tot++;
    }
    head++;
  }
  while (head > st) {
    head--;
    if (col[head] <= n) {
      if (num[col[head]] == col[head]) tot--;
      num[col[head]]++;
      if (num[col[head]] == col[head]) tot++;
    }
  }
  while (tail < ed) {
    tail++;
    if (col[tail] <= n) {
      if (num[col[tail]] == col[tail]) tot--;
      num[col[tail]]++;
      if (num[col[tail]] == col[tail]) tot++;
    }
  }
  while (tail > ed) {
    if (col[tail] <= n) {
      if (num[col[tail]] == col[tail]) tot--;
      num[col[tail]]--;
      if (num[col[tail]] == col[tail]) tot++;
    }
    tail--;
  }
}
void work() {
  for (long long i = 1; i <= m; i++) {
    move(query[i].l, query[i].r);
    ans[query[i].id] = tot;
  }
}
signed main() {
  n = read();
  m = read();
  for (long long i = 1; i <= n; i++) col[i] = read();
  for (long long i = 1; i <= m; i++) {
    query[i].l = read();
    query[i].r = read();
    query[i].id = i;
  }
  long long sqn = sqrt(n);
  for (long long i = 1; i <= n; i++) {
    if (i > cnt * sqn) cnt++;
    belong[i] = cnt;
  }
  sort(query + 1, query + m + 1, cmp1);
  work();
  for (long long i = 1; i <= m; i++) {
    printi(ans[i]);
    puts("");
  }
  return 0;
}
