#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > vv[300005];
int tree[300005 * 4];
int ans[300005];
int arr[300005];
void update(int node, int b, int e, int i) {
  if (b > i || e < i) return;
  if (b == e && b == i) {
    tree[node]++;
    return;
  }
  int left = 2 * node, right = left + 1, mid = (b + e) / 2;
  update(left, b, mid, i);
  update(right, mid + 1, e, i);
  tree[node] = tree[left] + tree[right];
}
int query1(int node, int b, int e, int v) {
  if (b == e) return b;
  int left = 2 * node, right = left + 1, mid = (b + e) / 2;
  int ret;
  if (tree[right] >= v)
    ret = query1(right, mid + 1, e, v);
  else
    ret = query1(left, b, mid, v - tree[right]);
  return ret;
}
int query(int node, int b, int e, int l, int r) {
  if (l > r) return 0;
  if (b > r || e < l) return 0;
  if (b >= l && e <= r) return tree[node];
  int left = 2 * node, right = left + 1, mid = (b + e) / 2;
  int p = query(left, b, mid, l, r);
  int q = query(right, mid + 1, e, l, r);
  int ret = p + q;
  return ret;
}
int main() {
  int n, q;
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);
  for (int i = 1; i <= q; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    vv[n - y].push_back(make_pair(x + 1, i));
  }
  for (int cs = 1; cs <= n; cs++) {
    if (cs - arr[cs] == 0)
      update(1, 1, n, cs);
    else if (cs - arr[cs] > 0 && cs - arr[cs] <= tree[1]) {
      int id = query1(1, 1, n, cs - arr[cs]);
      update(1, 1, n, id);
    }
    for (int i = 0; i < vv[cs].size(); i++) {
      ans[vv[cs][i].second] = query(1, 1, n, vv[cs][i].first, cs);
    }
  }
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
}
