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 _MAX(int a, int b) { return a > b ? a : b; }
int _MIN(int a, int b) { return a > b ? b : a; }
int Scan() {
  int res = 0, flag = 0;
  char ch;
  if ((ch = getchar()) == '-')
    flag = 1;
  else if (ch >= '0' && ch <= '9')
    res = ch - '0';
  while ((ch = getchar()) >= '0' && ch <= '9') res = res * 10 + (ch - '0');
  return flag ? -res : res;
}
void Out(int a) {
  if (a < 0) {
    putchar('-');
    a = -a;
  }
  if (a >= 10) Out(a / 10);
  putchar(a % 10 + '0');
}
int tree[100005], q[100005][3], a[100005], to[100005], n, m, ans[100005];
map<int, int> vis;
map<int, int> cou;
map<int, int> fuck;
int comp(const void *a, const void *b) { return *(int *)a - *(int *)b; }
void add(int x, int val) {
  while (x <= n) tree[x] += val, x += ((x) & (-x));
}
int sum(int x) {
  int ans = 0;
  while (x) ans += tree[x], x -= ((x) & (-x));
  return ans;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", a + i);
    cou[a[i]]++;
    if (cou[a[i]] == a[i])
      add(i, 1), fuck[a[i]] = i;
    else if (cou[a[i]] == a[i] + 1)
      add(i, -1);
    if (vis[a[i]]) to[vis[a[i]]] = i;
    vis[a[i]] = i;
  }
  for (int i = 1; i <= m; ++i) scanf("%d%d", &q[i][0], &q[i][1]), q[i][2] = i;
  qsort(q + 1, m, sizeof(q[1]), comp);
  int j = 1;
  for (int i = 1; i <= m; ++i) {
    while (j != q[i][0]) {
      int now = fuck[a[j]];
      if (now) add(now, -1);
      now = to[now];
      if (now) {
        add(now, 2);
        fuck[a[j]] = now;
        now = to[now];
        if (now) add(now, -1);
      } else
        fuck[a[j]] = 0;
      ++j;
    }
    ans[q[i][2]] = sum(q[i][1]) - sum(q[i][0] - 1);
  }
  for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
  return 0;
}
