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;
void fileIO() {}
long long GCD(long long A, long long B) { return (B) ? GCD(B, A % B) : A; }
long long LCM(long long A, long long B) { return A * B / GCD(A, B); }
long long max(long long A, long long B) { return (A >= B) ? A : B; }
long long min(long long A, long long B) { return (A <= B) ? A : B; }
long long bpow(long long A, long long B) {
  long long answer = 1;
  while (B > 0) {
    if (B & 1) {
      answer = answer * A;
    }
    A = A * A;
    B = B >> 1;
  }
  return answer;
}
long long bpow(long long A, long long B, long long MOD) {
  long long answer = 1;
  A %= MOD;
  while (B > 0) {
    if (B & 1) {
      answer = (answer * A) % MOD;
    }
    A = (A * A) % MOD;
    B = B >> 1;
  }
  return answer;
}
long long exGCD(long long A, long long B, long long &X, long long &Y) {
  if (B == 0) {
    X = 1;
    Y = 0;
    return A;
  }
  long long X1, Y1;
  long long gcd = exGCD(B, A % B, X1, Y1);
  X = Y1;
  Y = X1 - (Y1 * (A / B));
  return gcd;
}
long long modInv(long long A, long long M) {
  long long X, Y;
  long long gcd = exGCD(A, M, X, Y);
  if (gcd != 1) {
    cout << "A and M are NOT coprime"
         << "\n";
    return -1;
  } else {
    return (X % M + M) % M;
  }
}
long long modInvFormat(long long A, long long M) { return bpow(A, M - 2, M); }
const long long INF = (long long)1e18;
const long long NINF = -(long long)1e17;
const long long MOD = (long long)1e9 + 7;
long long n, q;
long long blk = 345;
long long ar[100005];
long long cnt = 0;
unordered_map<long long, long long> h;
struct query {
  long long l, r, id;
};
bool comp(query a, query b) {
  long long x = a.l / blk;
  long long y = b.l / blk;
  if (x != y) return x < y;
  if (x % 2)
    return a.r < b.r;
  else
    return a.r > b.r;
}
void add(long long index) {
  h[ar[index]]++;
  if (h[ar[index]] == ar[index]) {
    cnt++;
  } else if (h[ar[index]] == ar[index] + 1) {
    cnt--;
  }
}
void remove(long long index) {
  h[ar[index]]--;
  if (h[ar[index]] == ar[index]) {
    cnt++;
  } else if (h[ar[index]] == ar[index] - 1) {
    cnt--;
  }
}
void solve() {
  cin >> n >> q;
  for (long long i = (long long)1; i <= (long long)n; i++) {
    cin >> ar[i];
    h[ar[i]] = 0;
  }
  query qr[q];
  for (long long i = 0; i < (long long)q; i++) {
    cin >> qr[i].l >> qr[i].r;
    qr[i].id = i;
  }
  sort(qr, qr + q, comp);
  long long ans[q];
  long long currL = 1, currR = 0;
  for (long long i = 0; i < (long long)q; i++) {
    long long L = qr[i].l;
    long long R = qr[i].r;
    long long id = qr[i].id;
    while (currL > L) {
      currL--;
      add(currL);
    }
    while (currL < L) {
      remove(currL);
      currL++;
    }
    while (currR > R) {
      remove(currR);
      currR--;
    }
    while (currR < R) {
      currR++;
      add(currR);
    }
    ans[id] = cnt;
  }
  for (long long i = 0; i < (long long)q; i++) {
    cout << ans[i] << "\n";
  }
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  fileIO();
  long long Testcases = 1;
  for (long long testcase = 1; testcase <= Testcases; testcase++) {
    solve();
  }
  return 0;
}
