#include <bits/stdc++.h>
using namespace std;
long long a[300005], b[300005], f[300005], ans[300005];
pair<long long, pair<long long, long long>> z[300005];
long long sum(long long x) {
  if (x < 0)
    return 0;
  else
    return (f[x] + sum(((x + 1) & x) - 1));
}
int main() {
  long long n, q;
  cin >> n >> q;
  for (long long i = 0; i < n; i++) {
    cin >> a[n - i - 1];
    a[n - i - 1] = i - a[n - i - 1] + 1;
  }
  for (long long i = 0; i < q; i++) {
    cin >> z[i].second.first >> z[i].first;
    z[i].second.first = n - z[i].second.first - 1;
    z[i].second.second = i;
  }
  sort(z, z + q);
  long long k = 0;
  long long d = q - 1;
  for (long long i = n - 1; i >= 0; i--) {
    long long k = i;
    if (a[i] != 0) {
      long long r = n, l = i + 1;
      while (l < r) {
        k = (l + r) >> 1;
        if (sum(k) < a[i])
          l = k + 1;
        else
          r = k;
      }
      k = l;
    }
    if (a[i] < 0) k = n + 1;
    b[k]++;
    while (k <= n) {
      f[k]++;
      k = k | (k + 1);
    }
    while (d >= 0 && i == z[d].first) {
      ans[z[d].second.second] = sum(z[d].second.first);
      d--;
    }
  }
  for (long long i = 0; i < q; i++) cout << ans[i] << endl;
  return 0;
}
