#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 1;
int N, Q, nums[MAXN], ans[MAXN], BIT[MAXN + 5];
vector<pair<int, int> > queries[MAXN];
void upd(int i) {
  i++;
  while (i > 0) {
    BIT[i]++;
    i -= i & -i;
  }
}
int get(int i) {
  i++;
  int ret = 0;
  while (i < N + 5) {
    ret += BIT[i];
    i += i & -i;
  }
  return ret;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> N >> Q;
  for (int i = 1; i <= N; i++) {
    cin >> nums[i];
    nums[i] = i - nums[i];
  }
  for (int i = 0; i < Q; i++) {
    int x, y;
    cin >> x >> y;
    if (x + y >= N) {
      ans[i] = 0;
      continue;
    }
    queries[N - y].push_back(make_pair(1 + x, i));
  }
  for (int i = 1; i <= N; i++) {
    if (nums[i] >= 0 && get(1) >= nums[i]) {
      int lo = 1;
      int hi = i;
      if (nums[i] == 0) lo = i;
      while (lo < hi - 1) {
        int m = (lo + hi) / 2;
        if (get(m) >= nums[i]) {
          lo = m;
        } else {
          hi = m;
        }
      }
      upd(lo);
    }
    for (auto it : queries[i]) {
      ans[it.second] = get(it.first);
    }
  }
  for (int i = 0; i < Q; i++) {
    cout << ans[i] << "\n";
  }
}
