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>
#pragma comment(linker, "/STACK:60000000")
using namespace std;
struct debugger {
  template <typename T>
  debugger& operator,(const T& v) {
    cerr << v << "\t";
    return *this;
  }
} dbg;
template <class T>
void setmax(T& a, T b) {
  if (a < b) a = b;
}
template <class T>
void setmin(T& a, T b) {
  if (b < a) a = b;
}
template <class T>
T Abs(T x) {
  return x > 0 ? x : -x;
}
template <class T>
inline T sqr(T x) {
  return x * x;
}
template <class T>
inline T Mod(T n, T m) {
  return (n % m + m) % m;
}
template <class T>
string toString(T n) {
  ostringstream oss;
  oss << n;
  oss.flush();
  return oss.str();
}
int toInt(string s) {
  int r = 0;
  istringstream sin(s);
  sin >> r;
  return r;
}
bool isVowel(char ch) {
  ch = tolower(ch);
  if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u')
    return true;
  return false;
}
bool isUpper(char c) { return c >= 'A' && c <= 'Z'; }
bool isLower(char c) { return c >= 'a' && c <= 'z'; }
long long Pow(long long B, long long P) {
  long long R = 1;
  while (P > 0) {
    if (P % 2 == 1) R = (R * B);
    P /= 2;
    B = (B * B);
  }
  return R;
}
int BigMod(long long B, long long P, long long M) {
  long long R = 1;
  while (P > 0) {
    if (P % 2 == 1) {
      R = (R * B) % M;
    }
    P /= 2;
    B = (B * B) % M;
  }
  return (int)R;
}
void binprint(long long mask, long long n) {
  long long i;
  string s = "";
  do {
    s += (mask % 2 + '0');
    mask /= 2;
  } while (mask);
  reverse(s.begin(), s.end());
  s = string(max(n - (int)s.size(), 0LL), '0') + s;
  for (i = (int)s.size() - n; i < (int)s.size(); i++) printf("%c", s[i]);
  printf("\n");
}
void ASCII_Chart() {
  int i, j, k;
  printf("ASCII Chart:(30-129)\n");
  for (i = 30; i < 50; i++) {
    for (j = 0; j < 5; j++) {
      k = i + j * 20;
      printf("%3d---> '%c'   ", k, k);
    }
    printf("\n");
  }
}
vector<int> adj[110000];
int dp[510][110000], store[510];
int arr[110000];
int main() {
  int i, j, test, Case = 1, ans, N, M, k, ind, l, r, cnt, val;
  while (scanf("%d %d", &N, &M) == 2) {
    for (i = 0; i < N + 1; i++) adj[i].clear();
    for (i = 0; i < N; i++) {
      scanf("%d", &arr[i]);
      if (arr[i] <= N) adj[arr[i]].push_back(i);
    }
    k = 0;
    for (i = 1; i < N + 1; i++) {
      if ((int)adj[i].size() >= i) {
        store[k++] = i;
      }
    }
    memset(dp, 0, sizeof(dp));
    for (i = 0; i < k; i++) {
      for (j = 0; j < (int)adj[store[i]].size(); j++) {
        ind = adj[store[i]][j];
        dp[i][ind] = 1;
      }
    }
    for (i = 0; i < k; i++) {
      for (j = 1; j <= N; j++) dp[i][j] += dp[i][j - 1];
    }
    for (i = 0; i < M; i++) {
      scanf("%d %d", &l, &r);
      l--;
      r--;
      ans = 0;
      for (j = 0; j < k; j++) {
        val = store[j];
        if (l == 0)
          cnt = dp[j][r];
        else
          cnt = dp[j][r] - dp[j][l - 1];
        if (cnt == val) ans++;
      }
      printf("%d\n", ans);
    }
  }
  return 0;
}
