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;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
string vow = "aeiou";
int month[] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int dxhorse[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dyhorse[] = {1, -1, 2, -2, 2, -2, 1, -1};
const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
const long double pie = 3.1415926535897932384626;
const long long mod = 1e9 + 7;
const int N = 1e5 + 2;
int n, q;
int v[N];
array<int, 3> qry[N];
const int z = 300;
void read() {
  cin >> n >> q;
  for (int i = 0; i < n; i++) cin >> v[i];
  for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    qry[i] = {l, r, i};
  }
}
bool comp(const array<int, 3> &a, const array<int, 3> &b) {
  int c_a = a[0] / z;
  int c_b = b[0] / z;
  if (c_a != c_b) return a < b;
  if (c_a & 1)
    return a[1] < b[1];
  else
    return a[1] > b[1];
}
void MO() { sort(qry, qry + q, comp); }
int ans = 0;
int freq[N + 10];
void add(const int &indx) {
  int val = v[indx];
  if (val > n) return;
  if (freq[val] == val) ans--;
  freq[val]++;
  if (freq[val] == val) ans++;
}
void del(const int &indx) {
  int val = v[indx];
  if (val > n) return;
  if (freq[val] == val) ans--;
  freq[val]--;
  if (freq[val] == val) ans++;
}
void solve(int test_case) {
  read();
  MO();
  int p1 = 0, p2 = -1;
  vector<int> ans(q);
  for (int i = 0; i < q; i++) {
    int l = qry[i][0];
    int r = qry[i][1];
    int indx = qry[i][2];
    while (p2 < r) add(++p2);
    while (p2 > r) del(p2--);
    while (p1 < l) del(p1++);
    while (p1 > l) add(--p1);
    ans[indx] = ::ans;
  }
  for (int i = 0; i < q; i++) cout << ans[i], cout << "\n";
  ;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int t = 1;
  for (int i = 1; i <= t; i++) {
    solve(i);
  }
  return 0;
}
