#include <bits/stdc++.h>
using namespace std;
const int mxn = 5e5 + 10;
int n, q, ans[mxn], Tree[mxn], A[mxn];
vector<pair<int, int> > Q[mxn];
void update(int p, int val) {
  for (; p <= n; p += p & -p) Tree[p] += val;
}
int get(int p) {
  int sum = 0;
  for (; p > 0; p -= p & -p) sum += Tree[p];
  return sum;
}
int bin(int x, int r, int l = 0, int mid = 0) {
  while (r - l > 1) {
    mid = (l + r) / 2;
    if (get(mid) < x)
      r = mid;
    else
      l = mid;
  }
  return r;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> A[i];
    A[i] = i - A[i];
  }
  for (int i = 1; i <= q; i++) {
    int x, y;
    cin >> x >> y;
    Q[n - y].push_back({x + 1, i});
  }
  for (int l = 1; l <= n; l++) {
    int now = A[l];
    if (now >= 0) {
      int ind = bin(now, l + 1);
      update(1, 1);
      update(ind, -1);
    }
    for (auto qq : Q[l]) ans[qq.second] = get(qq.first);
  }
  for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
}
