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 n, m;
int a[100100];
int ans;
map<int, int> counts;
vector<int> values;
int r[500][100100];
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    if (counts.count(a[i]) > 0) {
      counts[a[i]]++;
    } else {
      counts.insert(make_pair(a[i], 1));
    }
  }
  for (map<int, int>::iterator i = counts.begin(); i != counts.end(); i++) {
    if ((*i).second >= (*i).first) {
      values.push_back((*i).first);
    }
  }
  for (int i = 0; i < values.size(); i++) {
    if (a[0] == values[i]) r[i][0] = 1;
    for (int j = 1; j < n; j++) {
      r[i][j] = r[i][j - 1];
      if (a[j] == values[i]) r[i][j]++;
    }
  }
  for (int i = 0; i < m; i++) {
    int t1, t2;
    scanf("%d%d", &t1, &t2);
    t1--;
    t2--;
    ans = 0;
    for (int j = 0; j < values.size(); j++) {
      int temp = r[j][t2];
      if (t1 != 0) temp -= r[j][t1 - 1];
      if (temp == values[j]) ans++;
    }
    printf("%d\n", ans);
  }
  return 0;
}
