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 IINF = 1 << 28;
const double INF = 1e30;
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
int xs[100000];
int nums[500][100000];
int main() {
  int n, m;
  cin >> n >> m;
  map<int, int> cnt;
  for (int i = 0; i < n; ++i) {
    cin >> xs[i];
    cnt[xs[i]]++;
  }
  vector<int> vs;
  for (map<int, int>::iterator it = cnt.begin(); it != cnt.end(); it++) {
    if (it->second >= it->first) {
      vs.push_back(it->first);
      ;
    }
  }
  int len = vs.size();
  memset(nums, 0, sizeof(nums));
  for (int i = 0; i < len; ++i) {
    for (int j = 0; j < n; ++j) {
      nums[i][j + 1] = nums[i][j];
      if (vs[i] == xs[j]) {
        nums[i][j + 1]++;
      }
    }
  }
  for (int i = 0; i < m; ++i) {
    int l, r;
    cin >> l >> r;
    int res = 0;
    for (int j = 0; j < len; ++j) {
      if (nums[j][r] - nums[j][l - 1] == vs[j]) {
        res++;
      }
    }
    cout << res << endl;
  }
}
