#include <bits/stdc++.h>
using ll = long long;
using namespace std;
using namespace std::chrono;
int n, q;
int const N = 3e5 + 3;
int a[N];
int st[2][N];
vector<vector<int>> queries;
int ans[N];
struct Compare {
  bool operator()(const vector<int>& x, const vector<int>& y) {
    if (x[1] != y[1])
      return x[1] < y[1];
    else
      return make_pair(x[0], x[2]) < make_pair(y[0], y[2]);
  }
};
void upd(int typ, int pos, int val) {
  for (; pos < N; pos += (pos & (-pos))) st[typ][pos] += val;
}
int que(int typ, int pos) {
  int ret = 0;
  for (; pos; pos -= (pos & (-pos))) ret += st[typ][pos];
  return ret;
}
void upd_seg(int l, int r, int x) {
  upd(0, l, x);
  upd(0, r + 1, -x);
  upd(1, l, x * (l - 1));
  upd(1, r + 1, -x * r);
}
int prefix_sum(int l) { return que(0, l) * l - que(1, l); }
int binary_s(int l, int r, int k) {
  if (l == r) return l;
  int mid = (l + r) / 2;
  int ro = prefix_sum(mid + 1) - prefix_sum(mid);
  if (ro >= k)
    return binary_s(mid + 1, r, k);
  else
    return binary_s(l, mid, k);
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = (1); i <= (n); i++) {
    scanf("%d", &a[i]);
    a[i] = i - a[i];
  }
  for (int i = (1); i <= (q); i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    queries.push_back({a + 1, n - b, i});
  }
  int cnt = 0;
  sort(queries.begin(), queries.end(), Compare());
  if (a[1] == 0) upd_seg(1, 1, 1);
  while (cnt < queries.size() && queries[cnt][1] == 1) {
    ans[queries[cnt][2]] = prefix_sum(1);
    cnt++;
  }
  for (int i = (2); i <= (n); i++) {
    if (prefix_sum(1) >= a[i] && a[i] >= 0) {
      if (a[i]) {
        int w = binary_s(1, i - 1, a[i]);
        upd_seg(1, w, 1);
      } else
        upd_seg(1, i, 1);
    }
    while (cnt < queries.size() && queries[cnt][1] == i) {
      ans[queries[cnt][2]] =
          prefix_sum(queries[cnt][0]) - prefix_sum(queries[cnt][0] - 1);
      cnt++;
    }
  }
  for (int i = (1); i <= (q); i++) {
    printf("%d \n", ans[i]);
  }
  return 0;
}
