Let a_1, …, a_n be an array of n positive integers. In one operation, you can choose an index i such that a_i = i, and remove a_i from the array (after the removal, the remaining parts are concatenated).

The weight of a is defined as the maximum number of elements you can remove.

You must answer q independent queries (x, y): after replacing the x first elements of a and the y last elements of a by n+1 (making them impossible to remove), what would be the weight of a?

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 3 ⋅ 10^5) — the length of the array and the number of queries.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ n) — elements of the array.

The i-th of the next q lines contains two integers x and y (x, y ≥ 0 and x+y < n).

Output

Print q lines, i-th line should contain a single integer — the answer to the i-th query.

Examples

Input


13 5
2 2 3 9 5 4 6 5 7 8 3 11 13
3 1
0 0
2 4
5 0
0 12


Output


5
11
6
1
0


Input


5 2
1 4 1 2 4
0 0
1 0


Output


2
0

Note

Explanation of the first query:

After making first x = 3 and last y = 1 elements impossible to remove, a becomes [×, ×, ×, 9, 5, 4, 6, 5, 7, 8, 3, 11, ×] (we represent 14 as × for clarity).

Here is a strategy that removes 5 elements (the element removed is colored in red):

  * [×, ×, ×, 9, \color{red}{5}, 4, 6, 5, 7, 8, 3, 11, ×] 
  * [×, ×, ×, 9, 4, 6, 5, 7, 8, 3, \color{red}{11}, ×] 
  * [×, ×, ×, 9, 4, \color{red}{6}, 5, 7, 8, 3, ×] 
  * [×, ×, ×, 9, 4, 5, 7, \color{red}{8}, 3, ×] 
  * [×, ×, ×, 9, 4, 5, \color{red}{7}, 3, ×] 
  * [×, ×, ×, 9, 4, 5, 3, ×] (final state) 



It is impossible to remove more than 5 elements, hence the weight is 5.
#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000007;
int inf = 1000000000;
const int N = 300000;
struct segTreeSum {
  int* tree;
  int len;
  vector<int> input;
  segTreeSum(int l) {
    tree = new int[2 * (int)pow(2, ceil(log2(l))) - 1]{0};
    len = l;
    input.resize(l, 0);
  }
  segTreeSum(vector<int>& input, int l) {
    tree = new int[2 * (int)pow(2, ceil(log2(l))) - 1];
    len = l;
    this->input = input;
    constructTree(0, len - 1, 0);
  }
  void constructTree(int low, int high, int pos) {
    if (low == high) {
      tree[pos] = input[low];
      return;
    }
    int mid = (low + high) / 2;
    constructTree(low, mid, pos * 2 + 1);
    constructTree(mid + 1, high, pos * 2 + 2);
    tree[pos] = tree[pos * 2 + 2] + tree[pos * 2 + 1];
  }
  int query(int low, int high) { return rangeSum(low, high, 0, len - 1, 0); }
  int rangeSum(int qlow, int qhigh, int low, int high, int pos) {
    if (qlow <= low && qhigh >= high) {
      return tree[pos];
    }
    if (qlow > high || low > qhigh) {
      return 0;
    }
    int mid = (low + high) / 2;
    return rangeSum(qlow, qhigh, low, mid, pos * 2 + 1) +
           rangeSum(qlow, qhigh, mid + 1, high, pos * 2 + 2);
  }
  void update(int pos, int newVal) {
    update(pos, newVal - input[pos], 0, len - 1, 0);
    input[pos] = newVal;
  }
  void update(int i, int diff, int low, int high, int pos) {
    if (i > high || low > i) {
      return;
    }
    tree[pos] += diff;
    if (low != high) {
      int mid = (low + high) / 2;
      update(i, diff, low, mid, pos * 2 + 1);
      update(i, diff, mid + 1, high, pos * 2 + 2);
    }
  }
};
struct lazySegTreeMin {
  pair<int, int>* tree;
  int len;
  vector<int> lazy;
  lazySegTreeMin(const vector<int>& input, int l)
      : lazy(2 * (int)pow(2, ceil(log2(l))) - 1, 0) {
    int le = 2 * (int)pow(2, ceil(log2(l))) - 1;
    tree = new pair<int, int>[le];
    len = l;
    constructTree(0, len - 1, 0, input);
  }
  void constructTree(int low, int high, int pos, const vector<int>& input) {
    if (low == high) {
      tree[pos] = {low - input[low], -low};
      if (tree[pos].first < 0) {
        tree[pos].first = inf;
      }
      return;
    }
    int mid = (low + high) / 2;
    constructTree(low, mid, pos * 2 + 1, input);
    constructTree(mid + 1, high, pos * 2 + 2, input);
    tree[pos] = min(tree[pos * 2 + 2], tree[pos * 2 + 1]);
  }
  pair<int, int> query(int low, int high) {
    return rangeMin(low, high, 0, len - 1, 0);
  }
  pair<int, int> rangeMin(int qlow, int qhigh, int low, int high, int pos) {
    if (qlow > high || low > qhigh) {
      return {2147483600, 0};
    }
    if (lazy[pos] != 0) {
      tree[pos].first += lazy[pos];
      if (low != high) {
        lazy[pos * 2 + 1] += lazy[pos];
        lazy[pos * 2 + 2] += lazy[pos];
      }
      lazy[pos] = 0;
    }
    if (qlow <= low && qhigh >= high) {
      return tree[pos];
    }
    int mid = (low + high) / 2;
    return min(rangeMin(qlow, qhigh, low, mid, pos * 2 + 1),
               rangeMin(qlow, qhigh, mid + 1, high, pos * 2 + 2));
  }
  void update(int ql, int qh, int incr) { update(incr, ql, qh, 0, len - 1, 0); }
  void update(int incr, int ql, int qh, int low, int high, int pos) {
    if (lazy[pos] != 0) {
      tree[pos].first += lazy[pos];
      if (low != high) {
        lazy[pos * 2 + 1] += lazy[pos];
        lazy[pos * 2 + 2] += lazy[pos];
      }
      lazy[pos] = 0;
    }
    if (ql > high || low > qh) {
      return;
    }
    if (ql <= low && high <= qh) {
      tree[pos].first += incr;
      if (low != high) {
        lazy[pos * 2 + 2] += incr;
        lazy[pos * 2 + 1] += incr;
      }
      return;
    }
    int mid = (low + high) / 2;
    update(incr, ql, qh, low, mid, pos * 2 + 1);
    update(incr, ql, qh, mid + 1, high, pos * 2 + 2);
    tree[pos] = min(tree[pos * 2 + 1], tree[pos * 2 + 2]);
  }
};
vector<int> arr;
vector<pair<int, int> > queries;
int ans[N];
int comp(int a, int b) { return queries[a] > queries[b]; }
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin.exceptions(cin.failbit);
  int n, q;
  cin >> n >> q;
  arr.resize(n);
  queries.resize(q);
  vector<int> srted(q);
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
    arr[i]--;
  }
  for (int i = 0; i < q; i++) {
    cin >> queries[i].first >> queries[i].second;
    queries[i].first--;
    srted[i] = i;
  }
  sort(srted.begin(), srted.end(), comp);
  lazySegTreeMin st(arr, n);
  segTreeSum sums(n);
  int cnt = 0;
  for (int i = 0; i < q; i++) {
    int x = queries[srted[i]].first;
    int y = queries[srted[i]].second;
    pair<int, int> curr = st.query(x + 1, n - 1);
    while (curr.first == 0) {
      st.update(-curr.second, -curr.second, inf);
      cnt++;
      sums.update(-curr.second, 1);
      st.update(-curr.second, n - 1, -1);
      curr = st.query(x + 1, n - 1);
    }
    int sub = 0;
    if (y > 0) {
      sub = sums.query(n - y, n - 1);
    }
    ans[srted[i]] = cnt - sub;
  }
  for (int i = 0; i < q; i++) {
    cout << ans[i] << "\n";
  }
}
