#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, flag = 1;
  char ch = getchar();
  for (; ch > '9' || ch < '0'; ch = getchar())
    if (ch == '-') flag = -1;
  for (; ch >= '0' && ch <= '9'; ch = getchar())
    x = (x << 3) + (x << 1) + ch - '0';
  return x * flag;
}
const int MAXN = 3e5 + 50;
int n, m, b[MAXN], Ans[MAXN];
struct SegmentTree {
  int l, r, Min, laz;
} T[MAXN << 2];
struct Ques {
  int l, r, id;
} Q[MAXN];
void ad(int x, int k) { T[x].Min += k, T[x].laz += k; }
void update(int x) { T[x].Min = min(T[x << 1].Min, T[x << 1 | 1].Min); }
bool cmp(Ques A, Ques B) { return A.r < B.r; }
void pushdown(int x) {
  ad(x << 1, T[x].laz), ad(x << 1 | 1, T[x].laz);
  T[x].laz = 0;
}
void build(int x, int l, int r) {
  T[x].l = l, T[x].r = r, T[x].laz = 0;
  if (l == r) return;
  build(x << 1, l, ((T[x].l + T[x].r) >> 1));
  build(x << 1 | 1, ((T[x].l + T[x].r) >> 1) + 1, r);
  return;
}
void change(int x, int l, int r) {
  if (T[x].l >= l && T[x].r <= r) {
    ad(x, 1);
    return;
  }
  pushdown(x);
  if (l <= ((T[x].l + T[x].r) >> 1)) change(x << 1, l, r);
  if (r > ((T[x].l + T[x].r) >> 1)) change(x << 1 | 1, l, r);
  update(x);
  return;
}
void modify(int x, int v) {
  if (T[x].l == T[x].r) {
    if (T[x].Min >= v) ad(x, 1);
    return;
  }
  pushdown(x);
  if (T[x << 1].Min >= v)
    ad(x << 1, 1), modify(x << 1 | 1, v);
  else
    modify(x << 1, v);
  update(x);
  return;
}
int GetAns(int x, int pos) {
  if (T[x].l == pos && T[x].r == pos) return T[x].Min;
  pushdown(x);
  if (pos <= ((T[x].l + T[x].r) >> 1))
    return GetAns(x << 1, pos);
  else
    return GetAns(x << 1 | 1, pos);
}
int main() {
  n = read(), m = read();
  for (int i = 1; i <= n; i++) b[i] = read() - i;
  for (int i = 1; i <= n; i++)
    if (b[i] > 0) b[i] = -1e9;
  build(1, 1, n);
  for (int i = 1; i <= m; i++)
    Q[i].l = read() + 1, Q[i].r = n - read(), Q[i].id = i;
  sort(Q + 1, Q + 1 + m, cmp);
  int now = 1;
  for (int i = 1; i <= n; i++) {
    int v = -b[i];
    if (v == 0 || v == 1e9) {
      if (v == 0) change(1, 1, i);
    } else
      modify(1, v);
    while (Q[now].r == i) Ans[Q[now].id] = GetAns(1, Q[now].l), now++;
  }
  for (int i = 1; i <= m; i++) printf("%d\n", Ans[i]);
  return 0;
}
