#include <bits/stdc++.h>
using namespace std;
long long n, m, tt = 1, num[300100], die[300100], ans[300100], id[300100];
struct Node {
  long long ls, rs, sum;
} node[300100 << 1];
struct Que {
  long long id, x, y;
  bool operator<(const Que &u) const { return x > u.x; }
} que[300100];
struct Sz {
  long long num[300100];
  inline long long lb(long long u) { return u & (-u); }
  inline void add(long long u, long long v) {
    for (; u; u += lb(u)) num[u] += v;
  }
  inline long long ask(long long u) {
    long long res = 0;
    for (; u; u -= lb(u)) res += num[u];
    return res;
  }
} sz;
void build(long long now, long long l, long long r) {
  if (l == r) return;
  long long mid = ((l + r) >> 1);
  node[now].ls = ++tt;
  build(tt, l, mid);
  node[now].rs = ++tt;
  build(tt, mid + 1, r);
}
void add(long long now, long long l, long long r, long long u) {
  if (l == r) {
    node[now].sum++;
    return;
  }
  node[now].sum++;
  long long mid = ((l + r) >> 1);
  if (u <= mid)
    add(node[now].ls, l, mid, u);
  else
    add(node[now].rs, mid + 1, r, u);
}
long long ask_k(long long now, long long l, long long r, long long u) {
  if (l == r) return l;
  long long mid = ((l + r) >> 1);
  if (u <= node[node[now].rs].sum)
    return ask_k(node[now].rs, mid + 1, r, u);
  else
    return ask_k(node[now].ls, l, mid, u - node[node[now].rs].sum);
}
void clear(long long now, long long l, long long r) {
  if (l == r) {
    node[now].sum = 0;
    return;
  }
  node[now].sum = 0;
  long long mid = ((l + r) >> 1);
  clear(node[now].ls, l, mid);
  clear(node[now].rs, mid + 1, r);
}
long long ask(long long now, long long l, long long r, long long u,
              long long v) {
  if (u <= l && r <= v) return node[now].sum;
  long long res = 0, mid = ((l + r) >> 1);
  if (u <= mid) res += ask(node[now].ls, l, mid, u, v);
  if (v > mid) res += ask(node[now].rs, mid + 1, r, u, v);
  return res;
}
inline bool cmp(long long u, long long v) { return die[u] < die[v]; }
int main() {
  long long i, j, t = 0;
  cin >> n >> m;
  build(1, 1, n);
  for (i = 1; i <= n; i++) scanf("%lld", &num[i]);
  for (i = 1; i <= n; i++) {
    if (num[i] > i) continue;
    if (i - num[i] > t) continue;
    t++;
    if (num[i] == i) {
      die[i] = i;
      add(1, 1, n, i);
      continue;
    }
    die[i] = ask_k(1, 1, n, i - num[i]);
    add(1, 1, n, die[i]);
  }
  for (i = 1; i <= m; i++) {
    scanf("%lld%lld", &que[i].x, &que[i].y);
    que[i].y = n - que[i].y;
    que[i].id = i;
  }
  for (i = 1; i <= n; i++) id[i] = i;
  sort(que + 1, que + m + 1);
  sort(id + 1, id + n + 1, cmp);
  clear(1, 1, n);
  for (i = 1, t = n; i <= m; i++) {
    for (; die[id[t]] > que[i].x; t--) add(1, 1, n, id[t]);
    ans[que[i].id] = ask(1, 1, n, que[i].x + 1, que[i].y);
  }
  for (i = 1; i <= m; i++) printf("%lld\n", ans[i]);
}
