#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5;
int n, q, a[maxn + 5];
int arr[4 * maxn + 5], lazy[4 * maxn + 5], sum[4 * maxn + 5];
int ans[maxn + 5], res[maxn + 5];
vector<int> E[maxn + 5];
vector<pair<int, int> > Q[maxn + 5];
void pushup(int index) { arr[index] = max(arr[2 * index], arr[2 * index + 1]); }
void pushdown(int index) {
  arr[2 * index] += lazy[index];
  arr[2 * index + 1] += lazy[index];
  lazy[2 * index] += lazy[index];
  lazy[2 * index + 1] += lazy[index];
  lazy[index] = 0;
}
void modify(int index, int L, int R, int ML, int MR, int val) {
  if (L >= ML && R <= MR) {
    lazy[index] += val;
    arr[index] += val;
    return;
  }
  int mid = L + R >> 1;
  if (lazy[index]) pushdown(index);
  if (mid >= ML) modify(2 * index, L, mid, ML, MR, val);
  if (MR > mid) modify(2 * index + 1, mid + 1, R, ML, MR, val);
  pushup(index);
}
int query(int index, int L, int R, int val) {
  if (L == R) return L;
  int mid = L + R >> 1;
  if (lazy[index]) pushdown(index);
  if (arr[index] < val) return -1;
  if (arr[2 * index + 1] >= val)
    return query(2 * index + 1, mid + 1, R, val);
  else
    return query(2 * index, L, mid, val);
}
void update(int index, int L, int R, int pos, int val) {
  if (L == R) {
    sum[index] += val;
    return;
  }
  int mid = L + R >> 1;
  if (mid >= pos)
    update(2 * index, L, mid, pos, val);
  else
    update(2 * index + 1, mid + 1, R, pos, val);
  sum[index] = sum[2 * index] + sum[2 * index + 1];
}
int querysum(int index, int L, int R, int QL, int QR) {
  if (L >= QL && R <= QR) return sum[index];
  int mid = L + R >> 1, res = 0;
  if (mid >= QL) res += querysum(2 * index, L, mid, QL, QR);
  if (QR > mid) res += querysum(2 * index + 1, mid + 1, R, QL, QR);
  return res;
}
int main() {
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = 1; i <= n; ++i) {
    if (a[i] > i) {
      ans[i] = 0;
      continue;
    } else if (a[i] == i) {
      ans[i] = i;
      modify(1, 1, n, 1, i, 1);
    } else {
      int x = i - a[i];
      int pos = query(1, 1, n, x);
      if (pos == -1)
        ans[i] = 0;
      else {
        ans[i] = pos;
        modify(1, 1, n, 1, pos, 1);
      }
    }
  }
  for (int i = 1; i <= n; ++i)
    if (ans[i] != 0) {
      E[ans[i]].push_back(i);
      update(1, 1, n, i, 1);
    }
  for (int i = 1, x, y; i <= q; ++i) {
    scanf("%d %d", &x, &y);
    Q[x + 1].push_back(pair<int, int>(n - y, i));
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < Q[i].size(); ++j) {
      int y = Q[i][j].first, id = Q[i][j].second;
      res[id] = querysum(1, 1, n, 1, y);
    }
    for (int j = 0; j < E[i].size(); ++j) update(1, 1, n, E[i][j], -1);
  }
  for (int i = 1; i <= q; ++i) printf("%d\n", res[i]);
  return 0;
}
