#include <bits/stdc++.h>
using namespace std;
template <class S, class T>
S smax(S& a, const T b) {
  return a < b ? a = b : a;
}
template <class S, class T>
S smin(S& a, const T b) {
  return b < a ? a = b : a;
}
const int mod = 1000000007;
template <class T>
struct SegmentTree {
  T I, t[4];
  int N;
  vector<T> A;
  SegmentTree(int N, T I = T()) : I(I), N(N), A(2 * N, I) {}
  SegmentTree(const vector<T>& data, T I = T())
      : I(I), N(data.size()), A(2 * N, I) {
    copy(data.begin(), data.end(), A.begin() + N);
    for (int i = N - 1; i; i--) A[i].op(A[2 * i], A[2 * i + 1]);
  }
  void update(int i, T v) {
    for (A[i += N] = v; i /= 2;) A[i].op(A[2 * i], A[2 * i + 1]);
  }
  int query(int l, int r) {
    vector<int> rights;
    int ans = 0;
    int i = 0, j = 2;
    for (l += N, r += N; l < r; l /= 2, r /= 2) {
      if (l & 1) {
        A[l++].qop(ans);
        i ^= 1;
      }
      if (r & 1) {
        rights.push_back(--r);
        j ^= 1;
      }
    }
    while (rights.size()) {
      int cur = rights.back();
      rights.pop_back();
      A[cur].qop(ans);
    }
    return ans;
  }
};
struct SegVert {
  vector<pair<int, int> > a;
  void op(SegVert& b, SegVert& c) {
    a.clear();
    int i = 0, j = 0;
    int cc = 0, cb = 0;
    for (; i < b.a.size() || j < c.a.size();) {
      bool choosei = true;
      if (j < c.a.size()) {
        int jreq = c.a[j].first;
        if (i > 0)
          smin(jreq, b.a[i - 1].first + max(0, c.a[j].first - b.a[i - 1].first -
                                                   b.a[i - 1].second));
        if (i >= b.a.size() || jreq < b.a[i].first) {
          choosei = false;
          int jval = c.a[j].second;
          if (i > 0) jval += b.a[i - 1].second;
          if (a.size() > 0 && a.back().first == jreq)
            smax(a.back().second, jval);
          else
            a.emplace_back(jreq, jval);
          ++j;
        }
      }
      if (choosei) {
        int ireq = b.a[i].first;
        int ival = b.a[i].second + (j == 0 ? 0 : c.a[j - 1].second);
        if (a.size() > 0 && a.back().first == ireq)
          smax(a.back().second, ival);
        else
          a.emplace_back(ireq, ival);
        ++i;
      }
    }
  }
  void qop(int& cur) {
    int i = lower_bound(a.begin(), a.end(), pair<int, int>{cur, INT_MAX / 2}) -
            a.begin();
    --i;
    if (i >= 0) cur += a[i].second;
  }
};
int n, q;
vector<SegVert> datag;
void do_case() {
  cin >> n >> q;
  datag.resize(n);
  for (int i = 0; i < n; ++i) {
    int cur;
    cin >> cur;
    datag[i].a.emplace_back(i + 1 - cur, i + 1 - cur >= 0 ? 1 : 0);
  }
  SegmentTree<SegVert> st(datag);
  for (int i = 0; i < q; ++i) {
    int u, v;
    cin >> u >> v;
    cout << st.query(u, n - v) << '\n';
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  do_case();
}
