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 MAX_N = 100 * 1000 + 10, SQ = 444;
int n, m, a[MAX_N], l[MAX_N], r[MAX_N], id[MAX_N], cnt[MAX_N];
int ans[MAX_N], now_ans;
void read_input() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &l[i], &r[i]);
    l[i]--;
  }
}
bool cmp(int &i, int &j) {
  pair<int, int> x(l[i] / SQ, l[i] / SQ & 1 ? -r[i] : r[i]);
  pair<int, int> y(l[j] / SQ, l[j] / SQ & 1 ? -r[j] : r[j]);
  return x < y;
}
void pre() {
  iota(id, id + m, 0);
  sort(id, id + m, cmp);
}
inline void add(int v, int x) {
  if (v > n) return;
  now_ans -= cnt[v] == v;
  cnt[v] += x;
  now_ans += cnt[v] == v;
}
void mo() {
  int L = 0, R = 0;
  for (int tmp = 0; tmp < m; tmp++) {
    int i = id[tmp];
    while (R < r[i]) add(a[R++], +1);
    while (R > r[i]) add(a[--R], -1);
    while (L < l[i]) add(a[L++], -1);
    while (L > l[i]) add(a[--L], +1);
    ans[i] = now_ans;
  }
}
void solve() {
  pre();
  mo();
}
void print_output() {
  for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
}
int main() {
  read_input();
  solve();
  print_output();
}
