#include <bits/stdc++.h>
using namespace std;
const int maxn = 300000, maxm = 300000, maxt = maxn << 2;
int n, m, a[maxn + 5], D[maxn + 5], c[maxn + 5], ans[maxm + 5];
struct data {
  int L, R, id;
} q[maxm + 5];
int tag[maxt + 5], MIN[maxt + 5], ID[maxt + 5];
inline char readc() {
  static char buf[100000], *l = buf, *r = buf;
  return l == r && (r = (l = buf) + fread(buf, 1, 100000, stdin), l == r)
             ? EOF
             : *l++;
}
template <typename T>
int readi(T &x) {
  T tot = 0;
  char ch = readc(), lst = '+';
  while (!isdigit(ch)) {
    if (ch == EOF) return EOF;
    lst = ch;
    ch = readc();
  }
  while (isdigit(ch)) tot = (tot << 3) + (tot << 1) + (ch ^ 48), ch = readc();
  lst == '-' ? x = -tot : x = tot;
  return ((ch) == 10 || (ch) == 13 || (ch) == EOF);
}
inline bool cmp(const data &a, const data &b) { return a.L < b.L; }
void Insert(int x, int y) {
  for (int i = x; i <= n; i += i & -i) c[i] += y;
}
int Sum(int x) {
  int sum = 0;
  for (int i = x; i; i -= i & -i) sum += c[i];
  return sum;
}
void Build(int L, int R, int p = 1) {
  if (L == R) {
    MIN[p] = D[L];
    ID[p] = L;
    return;
  }
  int mid = L + (R - L >> 1);
  Build(L, mid, p << 1);
  Build(mid + 1, R, p << 1 | 1);
  if (MIN[p << 1] < MIN[p << 1 | 1])
    MIN[p] = MIN[p << 1], ID[p] = ID[p << 1];
  else
    MIN[p] = MIN[p << 1 | 1], ID[p] = ID[p << 1 | 1];
}
void Addtag(int p, int k) {
  MIN[p] += k;
  tag[p] += k;
}
void Pushdown(int p) {
  if (tag[p]) Addtag(p << 1, tag[p]), Addtag(p << 1 | 1, tag[p]), tag[p] = 0;
}
void Update(int pos, int l = 1, int r = n, int p = 1) {
  if (l == r) {
    MIN[p] = 1e9;
    return;
  }
  int mid = l + (r - l >> 1);
  Pushdown(p);
  if (pos <= mid)
    Update(pos, l, mid, p << 1);
  else
    Update(pos, mid + 1, r, p << 1 | 1);
  if (MIN[p << 1] < MIN[p << 1 | 1])
    MIN[p] = MIN[p << 1], ID[p] = ID[p << 1];
  else
    MIN[p] = MIN[p << 1 | 1], ID[p] = ID[p << 1 | 1];
}
void Dec(int L, int R, int l = 1, int r = n, int p = 1) {
  if (L == l && r == R) return Addtag(p, -1);
  int mid = l + (r - l >> 1);
  Pushdown(p);
  if (R <= mid)
    Dec(L, R, l, mid, p << 1);
  else if (L > mid)
    Dec(L, R, mid + 1, r, p << 1 | 1);
  else
    Dec(L, mid, l, mid, p << 1), Dec(mid + 1, R, mid + 1, r, p << 1 | 1);
  if (MIN[p << 1] < MIN[p << 1 | 1])
    MIN[p] = MIN[p << 1], ID[p] = ID[p << 1];
  else
    MIN[p] = MIN[p << 1 | 1], ID[p] = ID[p << 1 | 1];
}
void Delete(int k) {
  D[k] = 1e9;
  Insert(k, -1);
  Update(k);
  if (k < n) Dec(k + 1, n);
}
int main() {
  readi(n);
  readi(m);
  for (int i = 1; i <= n; i++) readi(a[i]);
  for (int i = 1; i <= m; i++)
    readi(q[i].L), q[i].L++, readi(q[i].R), q[i].R = n - q[i].R, q[i].id = i;
  for (int i = 1, now = 0; i <= n; i++)
    if (a[i] <= i && i - a[i] <= now)
      D[i] = now - (i - a[i]), now++, Insert(i, 1);
    else
      D[i] = 1e9;
  Build(1, n);
  sort(q + 1, q + m + 1, cmp);
  for (int i = 1, j = 1; i <= n; i++) {
    while (j <= m && q[j].L == i) ans[q[j].id] = Sum(q[j].R), j++;
    if (D[i] < 1e9) {
      Delete(i);
      while (MIN[1] < 0) Delete(ID[1]);
    }
  }
  for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
  return 0;
}
