#include <bits/stdc++.h>
using namespace std;
struct query {
  int x, y, id;
} q[300010];
struct node {
  int l, r, mn, tt, tg;
} t[1200010];
int n, Q, a[300010], nw, prt[300010];
vector<int> del;
bool cmp(query x, query y) { return x.x < y.x; }
void Build(const int& x, const int& l, const int& r) {
  t[x].l = l, t[x].r = r;
  if (l == r) return (void)(t[x].mn = (a[l] <= l ? a[l] - 1 : -1), t[x].tt = 1);
  int mid = l + r >> 1;
  Build(x << 1, l, mid), Build(x << 1 | 1, mid + 1, r),
      (t[x].mn = min(t[x << 1].mn, t[x << 1 | 1].mn),
       t[x].tt = t[x << 1].tt + t[x << 1 | 1].tt);
}
void Set(const int& x) {
  if (t[x].mn >= 0) return;
  if (t[x].l == t[x].r)
    return (void)(t[x].mn = 1e9, t[x].tt = 0, del.push_back(t[x].l));
  (t[x].tg ? t[x << 1].mn -= t[x].tg, t[x << 1 | 1].mn -= t[x].tg,
   t[x << 1].tg += t[x].tg, t[x << 1 | 1].tg += t[x].tg, t[x].tg = 0 : 0);
  Set(x << 1), Set(x << 1 | 1),
      (t[x].mn = min(t[x << 1].mn, t[x << 1 | 1].mn),
       t[x].tt = t[x << 1].tt + t[x << 1 | 1].tt);
}
bool Put(const int& x, const int& id) {
  if (t[x].l > id || t[x].r < id) return 0;
  if (t[x].l == t[x].r) return t[x].tt ? t[x].tt = 0, t[x].mn = 1e9, 1 : 0;
  (t[x].tg ? t[x << 1].mn -= t[x].tg, t[x << 1 | 1].mn -= t[x].tg,
   t[x << 1].tg += t[x].tg, t[x << 1 | 1].tg += t[x].tg, t[x].tg = 0 : 0);
  int tmp = (Put(x << 1, id) || Put(x << 1 | 1, id));
  (t[x].mn = min(t[x << 1].mn, t[x << 1 | 1].mn),
   t[x].tt = t[x << 1].tt + t[x << 1 | 1].tt);
  return tmp;
}
void Modify(const int& x, const int& id) {
  if (t[x].r < id) return;
  if (t[x].l >= id) return (void)(++t[x].tg, --t[x].mn);
  (t[x].tg ? t[x << 1].mn -= t[x].tg, t[x << 1 | 1].mn -= t[x].tg,
   t[x << 1].tg += t[x].tg, t[x << 1 | 1].tg += t[x].tg, t[x].tg = 0 : 0);
  Modify(x << 1, id), Modify(x << 1 | 1, id),
      (t[x].mn = min(t[x << 1].mn, t[x << 1 | 1].mn),
       t[x].tt = t[x << 1].tt + t[x << 1 | 1].tt);
}
int Query(const int& x, const int& id) {
  if (t[x].l > id) return 0;
  if (t[x].r <= id) return t[x].tt;
  (t[x].tg ? t[x << 1].mn -= t[x].tg, t[x << 1 | 1].mn -= t[x].tg,
   t[x << 1].tg += t[x].tg, t[x << 1 | 1].tg += t[x].tg, t[x].tg = 0 : 0);
  return Query(x << 1, id) + Query(x << 1 | 1, id);
}
int main() {
  scanf("%d%d", &n, &Q);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  Build(1, 1, n);
  do {
    for (int i = (int)del.size() - 1; i >= 0; --i)
      Modify(1, del[i]), del.pop_back();
    Set(1);
  } while (del.size());
  for (int i = 1; i <= Q; ++i) scanf("%d%d", &q[i].x, &q[i].y), q[i].id = i;
  sort(q + 1, q + Q + 1, cmp);
  for (int i = 1; i <= Q; ++i) {
    while (nw < q[i].x) ++nw, Put(1, nw) ? Modify(1, nw), 0 : 0;
    do {
      for (int i = (int)del.size() - 1; i >= 0; --i)
        Modify(1, del[i]), del.pop_back();
      Set(1);
    } while (del.size());
    prt[q[i].id] = Query(1, n - q[i].y);
  }
  for (int i = 1; i <= Q; ++i) printf("%d\n", prt[i]);
  return 0;
}
