#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 1;
int n, q, ar[N], bs, fen[N], ans[N];
vector<pair<int, int> > qry[N];
void update(int x, int v = -1) {
  for (; x <= n + 1; x += x & -x) fen[x] += v;
}
int query(int x) {
  int res = 0;
  for (; x; x -= x & -x) res += fen[x];
  return res;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) cin >> ar[i], ar[i] -= i;
  for (int i = 1; i <= q; i++) {
    int l, r;
    cin >> l >> r;
    qry[n - r].push_back(make_pair(i, l + 1));
  }
  for (int i = 1; i <= n; i++) {
    if (ar[i] <= 0 and bs + query(1) >= -ar[i]) {
      int lo = 1, hi = i + 1;
      while (lo < hi - 1) {
        int mid = lo + hi >> 1;
        if (bs + query(mid) >= -ar[i])
          lo = mid;
        else
          hi = mid;
      }
      bs++;
      update(hi);
    }
    for (auto [id, l] : qry[i]) ans[id] = bs + query(l);
  }
  for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
