#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
  if (!b) return a;
  return gcd(b, a % b);
}
long long fpow(long long a, long long b, long long mod) {
  long long res = 1ll;
  while (b) {
    if (b & 1) res = (res * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return res;
}
long long mul(long long a, long long b, long long mod) {
  long long res = 0;
  while (b) {
    if (b & 1) res = (res + a) % mod;
    a = (a + a) % mod;
    b >>= 1;
  }
  return res;
}
const long long mod = 1e9 + 7;
const double eps = 1e-3;
const double pi = acos(-1);
const long long N = 4e5 + 10;
long long a[N], b[N];
long long rt[N], ls[N * 20], rs[N * 20], sz[N * 20], tot;
void insert(long long &rt, long long last, long long l, long long r,
            long long p) {
  rt = ++tot;
  ls[rt] = ls[last], rs[rt] = rs[last];
  sz[rt] = sz[last] + 1;
  if (l == r) return;
  if (p <= ((l + r) >> 1))
    insert(ls[rt], ls[last], l, ((l + r) >> 1), p);
  else
    insert(rs[rt], rs[last], ((l + r) >> 1) + 1, r, p);
}
long long find(long long x, long long l, long long r, long long num) {
  if (l == r) return l;
  if (sz[rs[x]] >= num) return find(rs[x], ((l + r) >> 1) + 1, r, num);
  return find(ls[x], l, ((l + r) >> 1), num - sz[rs[x]]);
}
long long query(long long x, long long l, long long r, long long p) {
  if (l == r) return sz[x];
  if (p > ((l + r) >> 1)) return query(rs[x], ((l + r) >> 1) + 1, r, p);
  return query(ls[x], l, ((l + r) >> 1), p) + sz[rs[x]];
}
int main() {
  long long n, k;
  scanf("%lld %lld", &n, &k);
  for (long long i = 1; i <= n; i++) {
    long long x;
    scanf("%lld", &x);
    rt[i] = rt[i - 1];
    x = i - x;
    if (x < 0 || sz[rt[i - 1]] < x)
      continue;
    else if (!x)
      insert(rt[i], rt[i - 1], 0, n - 1, i - 1);
    else {
      long long lim = find(rt[i - 1], 0, n - 1, x);
      insert(rt[i], rt[i - 1], 0, n - 1, lim);
    }
  }
  while (k--) {
    long long x, y;
    scanf("%lld %lld", &x, &y);
    printf("%lld\n", query(rt[n - y], 0, n - 1, x));
  }
  return 0;
}
