#include <bits/stdc++.h>
using namespace std;
struct FenwickTree {
  vector<int> bit;
  int n;
  FenwickTree(int n) {
    this->n = n + 1;
    bit.assign(n + 1, 0);
  }
  FenwickTree(vector<int> a) : FenwickTree(a.size()) {
    for (size_t i = 0; i < a.size(); i++) add(i, a[i]);
  }
  int sum(int idx) {
    int ret = 0;
    for (++idx; idx > 0; idx -= idx & -idx) ret += bit[idx];
    return ret;
  }
  int bitSearch(int v, int r) {
    int pos = 0, sum = r - 1;
    if (v < 0) return pos;
    int t = log2(r);
    for (int i = t; i >= 0; i--) {
      if (pos + (1 << i) <= r && sum - bit[pos + (1 << i)] >= v) {
        pos += (1 << i);
        sum -= bit[pos];
      }
    }
    return pos;
  }
  int sum(int l, int r) { return sum(r) - sum(l); }
  void add(int idx, int delta) {
    for (++idx; idx < n; idx += idx & -idx) bit[idx] += delta;
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n, q, x, y;
  cin >> n >> q;
  vector<int> a;
  for (int i = 1; i <= n; i++) {
    cin >> x;
    a.push_back(i - x);
  }
  vector<vector<pair<int, int>>> que(n);
  vector<int> res(q, 0);
  for (int i = 0; i < q; i++) {
    cin >> x >> y;
    que[n - y - 1].push_back(make_pair(x, i));
  }
  FenwickTree F(n);
  for (int i = 0; i < n; i++) {
    int p = F.bitSearch(a[i], i + 1);
    F.add(p, 1);
    for (auto k : que[i]) {
      res[k.second] = i + 1 - F.sum(k.first);
    }
  }
  for (int i : res) {
    cout << i << "\n";
  }
}
