#include <bits/stdc++.h>
using namespace std;
long long n, q, c1, c2, c3 = 0, a[300001], abi[300002], s[300001];
pair<long long, pair<long long, long long>> aq[300001];
void update(long long xf, long long yf) {
  while (xf <= 300001) {
    abi[xf] += yf;
    xf += xf & (-xf);
  }
  return;
}
long long query(long long xf) {
  long long r = 0, c = 0;
  for (int i = 20; i >= 0; i--) {
    if (r + (1 << i) <= 300000) {
      if (c + abi[r + (1 << i)] >= xf) {
        c += abi[r + (1 << i)];
        r += (1 << i);
      }
    }
  }
  return r;
}
long long query1(long long xf) {
  long long r = 0;
  while (xf > 0) {
    r += abi[xf];
    xf -= xf & (-xf);
  }
  return r;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < q; i++) {
    cin >> aq[i].second.first >> aq[i].first;
    aq[i].first = n - aq[i].first;
    aq[i].second.first++;
    aq[i].second.second = i;
  }
  sort(aq, aq + q);
  c1 = 0;
  for (long long i = 1; i <= n; i++) {
    if (a[i] <= i) {
      long long te = query(i - a[i]);
      if (te > 0) {
        update(1, 1);
        update(min(te + 1, i + 1), -1);
      }
    }
    while (c1 < q && aq[c1].first == i) {
      s[aq[c1].second.second] = query1(aq[c1].second.first);
      c1++;
    }
  }
  for (int i = 0; i < q; i++) cout << s[i] << "\n";
}
