#include <bits/stdc++.h>
const int MAXN = 3e5 + 5;
int n, q, x, y, r;
int arr[MAXN], dp[MAXN], ans[MAXN];
int max_val[MAXN << 2], add[MAXN << 2];
struct node {
  int left, right, id;
  node(int left = 0, int right = 0, int id = 0) {
    this->left = left;
    this->right = right;
    this->id = id;
  }
  bool operator<(const node &x) const {
    if (right == x.right) {
      return left < x.left;
    } else {
      return right < x.right;
    }
  }
} que[MAXN];
void update(int cur) {
  max_val[cur] = std::max(max_val[cur << 1], max_val[(cur << 1) | 1]);
}
void caculate(int cur, int key) {
  max_val[cur] += key;
  add[cur] += key;
}
void pushdown(int cur) {
  caculate(cur << 1, add[cur]);
  caculate((cur << 1) | 1, add[cur]);
  add[cur] = 0;
}
void build(int cur, int left, int right) {
  if (left == right) {
    max_val[cur] = dp[left];
    return;
  }
  int mid = (left + right) >> 1;
  build(cur << 1, left, mid);
  build((cur << 1) | 1, mid + 1, right);
  update(cur);
}
void modify(int cur, int left, int right, int start, int end, int key) {
  if (left == start && right == end) {
    caculate(cur, key);
    return;
  }
  pushdown(cur);
  int mid = (left + right) >> 1;
  if (end <= mid)
    modify(cur << 1, left, mid, start, end, key);
  else if (start > mid)
    modify((cur << 1) | 1, mid + 1, right, start, end, key);
  else {
    modify(cur << 1, left, mid, start, mid, key);
    modify((cur << 1) | 1, mid + 1, right, mid + 1, end, key);
  }
  update(cur);
}
int query_place(int cur, int left, int right, int key) {
  if (max_val[cur] < key) return -1;
  if (left == right) return left;
  pushdown(cur);
  int mid = (left + right) >> 1;
  if (max_val[(cur << 1) | 1] >= key) {
    return query_place((cur << 1) | 1, mid + 1, right, key);
  } else {
    return query_place(cur << 1, left, mid, key);
  }
}
int query_ans(int cur, int left, int right, int p) {
  if (left == p && right == p) {
    return max_val[cur];
  }
  pushdown(cur);
  int mid = (left + right) >> 1;
  if (p <= mid)
    return query_ans(cur << 1, left, mid, p);
  else
    return query_ans((cur << 1) | 1, mid + 1, right, p);
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &arr[i]);
    arr[i] = i - arr[i];
  }
  for (int i = 1; i <= q; ++i) {
    scanf("%d%d", &x, &y);
    que[i].left = x + 1;
    que[i].right = n - y;
    que[i].id = i;
  }
  std::sort(que + 1, que + q + 1);
  if (arr[1] == 0) dp[1] = 1;
  build(1, 1, n);
  r = 1;
  for (int i = 1; i <= q; ++i) {
    while (r < que[i].right) {
      ++r;
      if (arr[r] >= 0) {
        int place = std::min(r, query_place(1, 1, n, arr[r]));
        if (place != -1) {
          modify(1, 1, n, 1, place, 1);
        }
      }
    }
    ans[que[i].id] = query_ans(1, 1, n, que[i].left);
  }
  for (int i = 1; i <= q; ++i) {
    printf("%d\n", ans[i]);
  }
  return 0;
}
