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;
long long int sum() { return 0; }
template <typename T, typename... Args>
T sum(T a, Args... args) {
  return a + sum(args...);
}
struct Timer {
  chrono::time_point<chrono::high_resolution_clock> start, end;
  chrono::duration<float> dur;
  Timer() { start = chrono::high_resolution_clock::now(); }
  ~Timer() {
    end = chrono::high_resolution_clock::now();
    dur = end - start;
    cout << "\nTime Elapsed : " << dur.count() << " s\n";
  }
};
template <typename T>
class SieveEratosthenes {
 public:
  vector<T> primes;
  vector<bool> is_prime;
  SieveEratosthenes(int MAX = 1000000) {
    is_prime.resize(MAX + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (long long int i = 2; i * i <= MAX; i++)
      if (is_prime[i])
        for (long long int j = i * i; j <= MAX; j += i) is_prime[j] = false;
    for (long long int i = 2; i <= MAX; i++)
      if (is_prime[i]) primes.push_back(i);
  }
};
template <typename T>
class SieveEuler {
 public:
  vector<T> primes;
  vector<T> lp;
  inline SieveEuler(int MAX = 1000000) {
    lp.resize(MAX + 1, 0);
    for (long long int i = 2; i <= MAX; i++) {
      if (lp[i] == 0) {
        lp[i] = i;
        primes.push_back(i);
      }
      for (int j = 0;
           j < primes.size() && i * primes[j] <= MAX && primes[j] <= lp[i];
           ++j) {
        if (primes[j] == lp[i]) {
          lp[i * primes[j]] = primes[j];
        } else {
          lp[i * primes[j]] = primes[j];
        }
      }
    }
  }
};
long long int EulerPhi(long long int n) {
  long long int result = n;
  for (long long int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      while (n % i == 0) n /= i;
      result -= result / i;
    }
  }
  if (n > 1) result -= result / n;
  return result;
}
template <typename T>
vector<vector<T>> matmul(const vector<vector<T>>& a,
                         const vector<vector<T>>& b) {
  int n = a.size(), m = b[0].size(), k = b.size();
  vector<vector<T>> c(n, vector<T>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      for (int l = 0; l < k; l++) c[i][j] += (a[i][k] * b[k][j]);
    }
  }
  return c;
}
template <typename T>
T extended_euclid(T a, T b, vector<T>& X) {
  if (b == 0) {
    X = {1, 0};
    return a;
  } else {
    T g = extended_euclid(b, a % b, X);
    vector<vector<T>> G = {{0LL, 1LL}, {1LL, -(a / b)}};
    X = matmul<T>(G, X);
    return g;
  }
}
template <typename T>
bool isPrime(T n) {
  if (n <= 1)
    return false;
  else if (n == 2 || n == 3)
    return true;
  else if (n % 2 == 0 || n % 3 == 0)
    return false;
  T x = 5;
  T p = 2;
  while (x * x <= n) {
    if (n % x == 0) return true;
    x += p;
    p = 6 - p;
  }
  return true;
}
long long int binpow(long long int x, long long int n,
                     long long int mod = 1000000007) {
  long long int ans = 1;
  x = x % mod;
  while (n >= 1) {
    if (n & 1) ans = (ans * x) % mod;
    x = (x * x) % mod;
    n >>= 1;
  }
  return ans;
}
long long int gcd(long long int a, long long int b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
template <typename T>
class Graph {
 public:
  int n;
  vector<vector<T>> adj;
  bool directed;
  Graph(int n, bool directed = false) {
    this->n = n;
    adj.resize(n + 1);
    this->directed = directed;
  }
  void add_edge(int u, int v) {
    adj[u].push_back(v);
    if (!directed) adj[v].push_back(u);
  }
  void add_edge(int u, int v, int w) {
    adj[u].push_back({v, w});
    if (!directed) adj[v].push_back({u, w});
  }
};
class DisjointSets {
 public:
  int n;
  vector<int> parent;
  vector<int> rank;
  vector<int> sz;
  DisjointSets(int n, bool Rank = true) {
    this->n = n;
    parent.resize(n + 1, 0);
    iota(parent.begin(), parent.end(), 0);
    (Rank ? rank.resize(n + 1, 1) : sz.resize(n + 1, 1));
  }
  int find(int i) {
    if (i != parent[i]) parent[i] = find(parent[i]);
    return parent[i];
  }
  void UnionByRank(int i, int j) {
    i = find(i);
    j = find(j);
    if (i == j) return;
    if (rank[i] < rank[j]) swap(i, j);
    parent[j] = i;
    rank[i] += rank[j];
  }
  void UnionBySize(int i, int j) {
    i = find(i);
    j = find(j);
    if (i == j) return;
    if (sz[i] < sz[j]) swap(i, j);
    parent[j] = i;
    sz[i] += sz[j];
  }
};
template <typename T>
class SegmentTree {
 public:
  vector<T> t;
  int n, H;
  void init(int n) {
    this->n = n;
    t.resize(2 * n);
    this->H = sizeof(int) * 8 - __builtin_clz(n);
  }
  void build() {
    for (int i = n - 1; i > 0; i--) t[i] = t[i << 1] + t[(i << 1) | 1];
  }
  void update(int pos, T val) {
    for (t[pos += n] += val; pos > 1; pos >>= 1)
      t[pos >> 1] = t[pos] + t[pos ^ 1];
  }
  T query(int l, int r) {
    T res = 0;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) res += t[l++];
      if (r & 1) res += t[--r];
    }
    return res;
  }
};
bool isSubsequenceString(string x, string y) {
  int i = 0, j = 0;
  while (i < x.length() && j < y.length()) x[i] == y[j] ? i++, j++ : i++;
  return (j == y.length());
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> freq(n + 1);
  vector<pair<int, vector<int>>> a;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (x <= n) freq[x].push_back(i + 1);
  }
  for (int i = 1; i <= n; i++)
    if (freq[i].size() >= i) a.push_back({i, freq[i]});
  while (m--) {
    int l, r;
    cin >> l >> r;
    long long int ans = 0;
    for (int j = 0; j < a.size(); j++) {
      ans += (distance(lower_bound(a[j].second.begin(), a[j].second.end(), l),
                       lower_bound(a[j].second.begin(), a[j].second.end(),
                                   r + 1)) == a[j].first);
    }
    cout << ans << "\n";
  }
}
