#include <bits/stdc++.h>
using namespace std;
bool check(long long n, long long pos) { return n & (1LL << pos); }
long long Set(long long n, long long pos) { return n = n | (1LL << pos); }
struct BIT {
  vector<long long> tree;
  long long n;
  BIT(long long n) : n(n), tree(n + 3, 0) {}
  void init() { tree.assign(n + 3, 0); }
  long long query(long long idx) {
    long long sum = 0;
    while (idx > 0) {
      sum += tree[idx];
      idx -= idx & (-idx);
    }
    return sum;
  }
  void update(long long idx, long long x) {
    while (idx <= n) {
      tree[idx] += x;
      idx += idx & (-idx);
    }
  }
} bit(300002);
vector<pair<long long, long long> > en[300005];
long long arr[300005];
long long ans[300005];
long long bs(long long x, long long hi) {
  long long lo = 1;
  long long ret = hi;
  while (lo <= hi) {
    long long mid = (lo + hi) / 2;
    if (bit.query(mid) <= x) {
      ret = mid;
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  return ret;
}
int main() {
  long long i, j, k, l, m, n, o, r, q;
  long long testcase;
  long long input, flag, tag;
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  while (cin >> n >> m) {
    for (long long i = 1; i <= n; i++) en[i].clear();
    bit.init();
    for (long long i = 1; i <= n; i++) cin >> arr[i];
    for (long long i = 1; i <= m; i++) {
      long long x, y;
      cin >> x >> y;
      l = x + 1;
      r = n - y;
      en[r].push_back({l, i});
    }
    for (long long i = 1; i <= n; i++) arr[i] = i - arr[i];
    long long tot = 0;
    for (long long i = 1; i <= n; i++) {
      if (arr[i] >= 0 && tot >= arr[i]) {
        long long pos = bs(tot - arr[i], i);
        tot++;
        bit.update(pos + 1, 1);
      }
      for (auto it : en[i]) {
        ans[it.second] = tot - bit.query(it.first);
      }
    }
    for (long long i = 1; i <= m; i++) {
      cout << ans[i] << "\n";
    }
  }
}
