#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
int n, v[N], bg[N];
int BIT[N];
void add(int idx, int val) {
  while (idx <= n) {
    BIT[idx] += val;
    idx += idx & -idx;
  }
}
int get(int idx) {
  int ret = 0;
  while (idx) {
    ret += BIT[idx];
    idx -= idx & -idx;
  }
  return ret;
}
vector<int> seg[4 * N];
void build(int n, int s, int e) {
  if (s == e) {
    if (bg[s] != -1) seg[n] = {bg[s]};
    return;
  }
  build(n * 2, s, (s + e) / 2);
  build(n * 2 + 1, (s + e) / 2 + 1, e);
  const auto& a = seg[n * 2];
  const auto& b = seg[n * 2 + 1];
  seg[n].reserve(a.size() + b.size());
  int i = 0, j = 0;
  while (i < a.size() && j < b.size()) {
    if (a[i] < b[j])
      seg[n].push_back(a[i++]);
    else
      seg[n].push_back(b[j++]);
  }
  while (i < a.size()) seg[n].push_back(a[i++]);
  while (j < b.size()) seg[n].push_back(b[j++]);
}
int l, r, val;
int get(int n, int s, int e) {
  if (r < s || l > e) return 0;
  if (s >= l && e <= r)
    return seg[n].size() -
           (lower_bound(seg[n].begin(), seg[n].end(), val) - seg[n].begin());
  return get(n * 2, s, (s + e) / 2) + get(n * 2 + 1, (s + e) / 2 + 1, e);
}
int main() {
  int q;
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &v[i]);
    int need = i - v[i];
    bg[i] = -1;
    if (need >= 0) {
      int l = 1, r = i, m, at = -1;
      while (l <= r) {
        m = (l + r) / 2;
        if (get(i) - get(m - 1) >= need) {
          at = m;
          l = m + 1;
        } else
          r = m - 1;
      }
      if (at != -1) {
        add(at, 1);
        bg[i] = at;
      }
    }
  }
  build(1, 1, n);
  while (q--) {
    scanf("%d%d", &l, &r);
    ++l;
    r = n - r;
    val = l;
    printf("%d\n", get(1, 1, n));
  }
  return 0;
}
