#include <bits/stdc++.h>
using namespace std;
struct Node : pair<int, int> {
 public:
  int& min = first;
  int& cnt = second;
  int lazy = 0;
  int l;
  int r;
};
class SegmentTree {
 private:
  int sz;
  vector<Node> nodes;

 public:
  SegmentTree() {}
  SegmentTree(int _sz) {
    sz = _sz;
    nodes.resize(sz * 4);
  }
  SegmentTree(const vector<int>& data) {
    sz = (int)data.size();
    nodes.resize(sz * 4);
    build(1, 0, sz - 1, data);
  }
  void build(int node, int l, int r, const vector<int>& data) {
    nodes[node].l = l;
    nodes[node].r = r;
    if (l == r) {
      nodes[node].cnt = 0;
      nodes[node].min = data[l];
    } else {
      build(node * 2, l, (l + r) / 2, data);
      build(node * 2 + 1, (l + r) / 2 + 1, r, data);
      nodes[node].cnt = nodes[node * 2].cnt + nodes[node * 2 + 1].cnt;
      nodes[node].min = min(nodes[node * 2].min, nodes[node * 2 + 1].min);
    }
  }
  void push(int node, int l, int r) {
    if (l < r) {
      nodes[node * 2].min += nodes[node].lazy;
      nodes[node * 2 + 1].min += nodes[node].lazy;
      nodes[node * 2].lazy += nodes[node].lazy;
      nodes[node * 2 + 1].lazy += nodes[node].lazy;
    }
    nodes[node].lazy = 0;
  }
  void update_cnt(int node, int l, int r, int t, int delta) {
    push(node, l, r);
    if (l > t or r < t) return;
    if (l == t and r == t) {
      nodes[node].cnt += delta;
      nodes[node].min = INF;
    } else {
      update_cnt(node * 2, l, (l + r) / 2, t, delta);
      update_cnt(node * 2 + 1, (l + r) / 2 + 1, r, t, delta);
      nodes[node].cnt = nodes[node * 2].cnt + nodes[node * 2 + 1].cnt;
      nodes[node].min = min(nodes[node * 2].min, nodes[node * 2 + 1].min);
    }
  }
  void update(int node, int l, int r, int tl, int tr, int delta) {
    push(node, l, r);
    if (l > tr or r < tl) return;
    if (tl <= l and r <= tr) {
      nodes[node].min += delta;
      nodes[node].lazy += delta;
    } else {
      update(node * 2, l, (l + r) / 2, tl, tr, delta);
      update(node * 2 + 1, (l + r) / 2 + 1, r, tl, tr, delta);
      nodes[node].min = min(nodes[node * 2].min, nodes[node * 2 + 1].min);
    }
  }
  int get(int node, int l, int r, int tl, int tr) {
    push(node, l, r);
    if (l > tr or r < tl) return 0;
    if (tl <= l and r <= tr) {
      return nodes[node].cnt;
    } else {
      return get(node * 2, l, (l + r) / 2, tl, tr) +
             get(node * 2 + 1, (l + r) / 2 + 1, r, tl, tr);
    }
  }
  pair<int, int> get_min(int node, int l, int r, int tl, int tr) {
    push(node, l, r);
    if (l > tr or r < tl)
      return {INF, node};
    else if (tl <= l and r <= tr) {
      return {nodes[node].min, node};
    } else {
      auto lft = get_min(node * 2, l, (l + r) / 2, tl, tr);
      auto rht = get_min(node * 2 + 1, (l + r) / 2 + 1, r, tl, tr);
      auto ans = rht;
      if (ans.first > lft.first) {
        ans.first = lft.first;
        ans.second = lft.second;
      }
      return ans;
    }
  }
  int get_min_ind(int node) {
    push(node, nodes[node].l, nodes[node].r);
    if (nodes[node].l == nodes[node].r) {
      return nodes[node].l;
    } else {
      if (nodes[node * 2 + 1].min == 0) {
        return get_min_ind(node * 2 + 1);
      } else {
        return get_min_ind(node * 2);
      }
    }
  }
  void print(int node, int l, int r) {
    push(node, l, r);
    if (l == r) {
      cerr << nodes[node].min << ' ';
    } else {
      print(node * 2, l, (l + r) / 2);
      print(node * 2 + 1, (l + r) / 2 + 1, r);
    }
  }
  void print() { print(1, 0, sz - 1); }
  void print_cnt(int node, int l, int r) {
    push(node, l, r);
    if (l == r) {
      cerr << nodes[node].cnt << ' ';
    } else {
      print_cnt(node * 2, l, (l + r) / 2);
      print_cnt(node * 2 + 1, (l + r) / 2 + 1, r);
    }
  }
  void print_cnt() { print_cnt(1, 0, sz - 1); }
  static const int INF = 1e9;
};
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int n, q;
  cin >> n >> q;
  vector<int> a(n);
  for (auto& i : a) {
    cin >> i;
  }
  vector<int> ans(q, 0);
  vector<pair<int, pair<int, int>>> queries(q);
  for (auto& query : queries) {
    cin >> query.first >> query.second.first;
    query.second.first = n - 1 - query.second.first;
    query.second.second = &query - &queries[0];
  }
  sort(queries.begin(), queries.end());
  vector<int> distances(n);
  for (int i = 0; i < n; i++) {
    distances[i] = (i + 1) - (a[i]);
    if (distances[i] < 0) {
      distances[i] = SegmentTree::INF;
    }
  }
  SegmentTree st(distances);
  for (int i = n - 1; i >= 0; i--) {
    if (distances[i] == 0) {
      st.update_cnt(1, 0, n - 1, i, 1);
      st.update(1, 0, n - 1, i, n - 1, -1);
    }
    while (true) {
      auto [mn_val, mn_node] = st.get_min(1, 0, n - 1, i, n - 1);
      if (mn_val > 0) {
        break;
      } else if (mn_val == 0) {
        auto mn_ind = st.get_min_ind(mn_node);
        st.update_cnt(1, 0, n - 1, mn_ind, 1);
        st.update(1, 0, n - 1, mn_ind, n - 1, -1);
      }
    }
    while (!queries.empty()) {
      auto query = queries.back();
      if (query.first == i) {
        auto an = st.get(1, 0, n - 1, query.first, query.second.first);
        ans[query.second.second] = an;
      } else {
        break;
      }
      queries.pop_back();
    }
  }
  for (auto an : ans) {
    cout << an << '\n';
  }
}
