#include <bits/stdc++.h>
using namespace std;
const int N = int(3e5) + 10;
int n, Q, a[N], Ans[N], pos[N], bit[N];
vector<int> End[N];
int main() {
  cin >> n >> Q;
  for (int i = (1), iend = (n); i <= iend; i++) cin >> a[i], a[i] = i - a[i];
  for (int i = 1, x, y, l, r; i <= Q; i++)
    cin >> x >> y, l = 1 + x, r = n - y, pos[i] = l, End[r].push_back(i);
  for (int r = 1, res = 0, ar; ar = a[r], r <= n; r++) {
    if (ar >= 0) {
      int cp = 0, cur = res, t = 0;
      for (int nn = n; nn; nn >>= 1, t++)
        ;
      for (int k = 1 << t; k; k >>= 1)
        if (cp + k <= r && cur - bit[cp + k] >= ar) cp += k, cur -= bit[cp];
      res++;
      for (int i = cp + 1; i <= n; i += (i & -i)) bit[i]++;
    }
    for (int _t = (0), _tend = ((int)End[r].size() - 1); _t <= _tend; _t++) {
      int t = End[r][_t];
      Ans[t] = res;
      for (int i = pos[t]; i; i -= (i & (-i))) Ans[t] -= bit[i];
    }
  }
  for (int i = (1), iend = (Q); i <= iend; i++) cout << Ans[i] << "\n";
  return 0;
}
