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 = (int)1e5 + 10;
int a[MAXN], n, m;
vector<int> pos[MAXN];
int pre[MAXN];
int last[MAXN];
int c[MAXN];
struct node {
  int l, r, id, res;
} q[MAXN];
bool cmp1(const node &a, const node &b) { return a.r < b.r; }
bool cmp2(const node &a, const node &b) { return a.id < b.id; }
void update(int x, int v) {
  if (x == 0) return;
  while (x <= n) {
    c[x] += v;
    x += x & -x;
  }
}
int getsum(int x) {
  int ret = 0;
  while (x > 0) {
    ret += c[x];
    x -= x & -x;
  }
  return ret;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    if (a[i] <= n) pos[a[i]].push_back(i);
  }
  memset(c, 0, sizeof(c));
  memset(last, 0, sizeof(last));
  memset(pre, 0, sizeof(pre));
  for (int x = 1; x <= n; x++) {
    for (int j = 1; j < pos[x].size(); j++) {
      last[pos[x][j]] = pos[x][j - 1];
    }
    for (int j = x - 1; j < pos[x].size(); j++)
      pre[pos[x][j]] = pos[x][j - x + 1];
  }
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &q[i].l, &q[i].r);
    q[i].id = i;
  }
  sort(q, q + m, cmp1);
  int st = 0;
  int lastr = 0;
  while (st < m) {
    int ed = st;
    while (ed < m && q[st].r == q[ed].r) ed++;
    for (int pos = lastr + 1; pos <= q[st].r; pos++) {
      update(pre[last[pos]], -1);
      update(last[pre[last[pos]]], 1);
      update(pre[pos], 1);
      update(last[pre[pos]], -1);
    }
    for (int i = st; i < ed; i++) {
      q[i].res = getsum(q[i].r) - getsum(q[i].l - 1);
    }
    lastr = q[st].r;
    st = ed;
  }
  sort(q, q + m, cmp2);
  for (int i = 0; i < m; i++) printf("%d\n", q[i].res);
  return 0;
}
