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;
struct QueryType {
  int l, r, id;
};
struct QueryType qu[100005];
int n, m, ai[100005], bi[100005], ans[100005], ci[100005], num[100005];
int size, now, bel[100005], blo;
inline void in(int &now) {
  char Cget = getchar();
  now = 0;
  while (Cget > '9' || Cget < '0') Cget = getchar();
  while (Cget >= '0' && Cget <= '9') {
    now = now * 10 + Cget - '0';
    Cget = getchar();
  }
}
bool cmp(QueryType aa, QueryType bb) {
  if (bel[aa.l] == bel[bb.l]) {
    if (bel[aa.r] == bel[bb.r]) {
      if (aa.l == bb.l)
        return aa.r < bb.r;
      else
        return aa.l < bb.l;
    } else
      return bel[aa.r] < bel[bb.r];
  } else
    return bel[aa.l] < bel[bb.l];
}
inline void updata(int x, int dis) {
  if (num[ai[x]] == ci[x]) now--;
  num[ai[x]] += dis;
  if (num[ai[x]] == ci[x]) now++;
}
int main() {
  in(n), in(m);
  for (int i = 1; i <= n; i++) in(ai[i]), bi[i] = ai[i], ci[i] = ai[i];
  sort(bi + 1, bi + n + 1), size = unique(bi + 1, bi + n + 1) - bi - 1;
  for (int i = 1; i <= n; i++)
    ai[i] = lower_bound(bi + 1, bi + size + 1, ai[i]) - bi;
  blo = sqrt(n);
  for (int i = 1; i <= n; i++) bel[i] = (i + 1) / blo;
  for (int i = 1; i <= m; i++) in(qu[i].l), in(qu[i].r), qu[i].id = i;
  sort(qu + 1, qu + m + 1, cmp);
  int l = 1, r = 0;
  for (int no = 1; no <= m; no++) {
    int ll = qu[no].l, rr = qu[no].r;
    if (l < ll)
      for (int i = l; i < ll; i++) updata(i, -1);
    else
      for (int i = l - 1; i >= ll; i--) updata(i, 1);
    if (r < rr)
      for (int i = r + 1; i <= rr; i++) updata(i, 1);
    else
      for (int i = r; i > rr; i--) updata(i, -1);
    l = ll, r = rr, ans[qu[no].id] = now;
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
