#include <bits/stdc++.h>
using namespace std;
const int nax = 3e5 + 1;
int n, q, ans[nax];
vector<int> a, dp, f, ra;
vector<pair<int, int>> vt[nax];
void update(vector<int> &f, int p, int k) {
  for (int i = p; i <= n; i += i & -i) {
    f[i] += k;
  }
}
int querry(vector<int> &f, int p) {
  int ans = 0;
  for (int i = p; i; i -= i & -i) {
    ans += f[i];
  }
  return ans;
}
int bs(int l, int r, int i) {
  while (l < r) {
    int mid = (l + r) / 2;
    if (a[i] - i + dp[i - 1] >= querry(f, mid))
      l = mid + 1;
    else
      r = mid;
  }
  return r;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> q;
  a.resize(n + 1);
  dp.resize(n + 1);
  f.resize(n + 1);
  ra.resize(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= q; i++) {
    int x, y;
    cin >> x >> y;
    y = n - y;
    vt[y].push_back({x, i});
  }
  for (int i = 1; i <= n; i++) {
    if (i >= a[i] && a[i] >= i - dp[i - 1]) {
      dp[i] = dp[i - 1] + 1;
    } else
      dp[i] = dp[i - 1];
  }
  for (int i = 1; i <= n; i++) {
    if (i >= a[i] && a[i] >= i - dp[i - 1]) {
      ra[i] = bs(1, i, i);
      update(f, ra[i], 1);
    }
    for (int j = 0; j < vt[i].size(); j++) {
      ans[vt[i][j].second] = dp[i] - querry(f, vt[i][j].first);
    }
  }
  for (int i = 1; i <= q; i++) cout << ans[i] << endl;
  return 0;
}
