#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n, q;
int tab[N];
pair<int, int> przed[N];
int kol[N];
int res[N];
int d[4 * N];
int push[4 * N];
int rozm;
bool comp(int a, int b) { return przed[a].second < przed[b].second; }
void add(int x, int ile) {
  d[x] += ile;
  push[x] += ile;
}
void pushuj(int x) {
  add(x * 2, push[x]);
  add(x * 2 + 1, push[x]);
  push[x] = 0;
}
void insert(int a, int b, int pocz, int kon, int x, int wart) {
  if (a <= pocz && kon <= b) {
    add(x, wart);
    return;
  }
  pushuj(x);
  int sr = (pocz + kon) / 2;
  if (a <= sr) {
    insert(a, b, pocz, sr, x * 2, wart);
  }
  if (sr < b) {
    insert(a, b, sr + 1, kon, x * 2 + 1, wart);
  }
  d[x] = min(d[x * 2], d[x * 2 + 1]);
}
void walk(int pocz, int kon, int x, int wart) {
  if (d[x] >= wart) {
    add(x, 1);
    return;
  }
  if (pocz == kon) {
    return;
  }
  pushuj(x);
  int sr = (pocz + kon) / 2;
  if (d[x * 2] >= wart) {
    walk(sr + 1, kon, x * 2 + 1, wart);
  }
  walk(pocz, sr, x * 2, wart);
  d[x] = min(d[x * 2], d[x * 2 + 1]);
}
int get(int a, int pocz, int kon, int x) {
  if (pocz == kon) {
    return d[x];
  }
  pushuj(x);
  int sr = (pocz + kon) / 2;
  if (a <= sr) {
    return get(a, pocz, sr, x * 2);
  } else {
    return get(a, sr + 1, kon, x * 2 + 1);
  }
}
void wypisz() {
  for (int i = 1; i <= n; i++) {
    printf("d[%d] = %d\n", i, get(i, 1, rozm, 1));
  }
  cout << endl;
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &tab[i]);
    tab[i] = i - tab[i];
  }
  for (int i = 1; i <= q; i++) {
    kol[i] = i;
    scanf("%d%d", &przed[i].first, &przed[i].second);
    przed[i] = {przed[i].first + 1, n - przed[i].second};
  }
  sort(kol + 1, kol + q + 1, comp);
  rozm = 1;
  while (rozm < n) {
    rozm *= 2;
  }
  insert(1, rozm, 1, rozm, 1, -1);
  int wsk = 1;
  for (int i = 1; i <= n; i++) {
    insert(i, i, 1, rozm, 1, 1);
    if (tab[i] >= 0) {
      walk(1, rozm, 1, tab[i]);
    }
    while (wsk <= q && przed[kol[wsk]].second == i) {
      res[kol[wsk]] = get(przed[kol[wsk]].first, 1, rozm, 1);
      wsk++;
    }
  }
  for (int i = 1; i <= q; i++) {
    printf("%d\n", res[i]);
  }
}
