#include <bits/stdc++.h>
using namespace std;
int n, q, a[300005], ans[300005];
vector<pair<int, int> > queries[300005];
int tree[1200006];
void upd(int l, int r, int pos, int x) {
  if (l == r) {
    tree[pos]++;
    return;
  }
  int mid = l + r >> 1;
  if (x <= mid)
    upd(l, mid, pos << 1, x);
  else
    upd(mid + 1, r, pos << 1 | 1, x);
  tree[pos]++;
}
int query(int l, int r, int pos, int x) {
  if (l == r) return r;
  int mid = l + r >> 1;
  if (tree[pos << 1] >= x)
    return query(l, mid, pos << 1, x);
  else
    return query(mid + 1, r, pos << 1 | 1, x - tree[pos << 1]);
}
int query1(int l, int r, int pos, int ql, int qr) {
  if (l >= ql && r <= qr) return tree[pos];
  if (l > qr || r < ql) return 0;
  int mid = l + r >> 1;
  return query1(l, mid, pos << 1, ql, qr) +
         query1(mid + 1, r, pos << 1 | 1, ql, qr);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 0; i < q; i++) {
    int x, y;
    cin >> x >> y;
    queries[n - y].push_back({x, i});
  }
  for (int i = 1; i <= n; i++) {
    if (a[i] > i)
      upd(0, n, 1, 0);
    else if (a[i] == i)
      upd(0, n, 1, i);
    else {
      int x = query(0, n, 1, a[i]);
      upd(0, n, 1, x);
    }
    for (auto p : queries[i]) {
      int x = query1(0, n, 1, 0, p.first);
      ans[p.second] = i - x;
    }
  }
  for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}
