#include <bits/stdc++.h>
#pragma GCC_optimize("O3", "unroll-loops")
using namespace std;
using pii = pair<int, int>;
void solve();
int find(int, int);
int lowbit(int);
int query(int);
void modify(int, int);
const int MAXN = 300005;
int n, q, in[MAXN], ans[MAXN], BIT[MAXN];
vector<pii> qu[MAXN];
int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  while (cin >> n >> q) solve();
  return 0;
}
void solve() {
  for (int i = 1; i <= n; ++i) cin >> in[i];
  for (int i = 1; i <= n; ++i) in[i] = i - in[i];
  for (int i = 1; i <= n; ++i) BIT[i] = 0;
  for (int i = 1; i <= n; ++i) qu[i].clear();
  for (int i = 1; i <= q; ++i) {
    int l, r;
    cin >> l >> r;
    r = n - r;
    l = l + 1;
    qu[r].push_back(make_pair(l, i));
  }
  for (int now = 1; now <= n; ++now) {
    int v = query(1);
    if (in[now] >= 0 && v >= in[now]) {
      int pt = find(in[now], now);
      modify(1, 1);
      modify(pt + 1, -1);
    }
    for (auto x : qu[now]) {
      ans[x.second] = query(x.first);
    }
  }
  for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}
int find(int v, int r) {
  int l, m;
  l = 1;
  while (l <= r) {
    m = (l + r) >> 1;
    if (query(m) >= v)
      l = m + 1;
    else
      r = m - 1;
  }
  return r;
}
int lowbit(int id) { return id & (-id); }
int query(int id) {
  int sum = 0;
  while (id) {
    sum += BIT[id];
    id -= lowbit(id);
  }
  return sum;
}
void modify(int id, int v) {
  while (id <= n) {
    BIT[id] += v;
    id += lowbit(id);
  }
}
