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;
template <typename A>
ostream& operator<<(ostream& cout, vector<A> const& v);
template <typename A, typename B>
ostream& operator<<(ostream& cout, pair<A, B> const& p) {
  return cout << "(" << p.first << ", " << p.second << ")";
}
template <typename A>
ostream& operator<<(ostream& cout, vector<A> const& v) {
  cout << "[";
  for (int i = 0; i < v.size(); i++) {
    if (i) cout << ", ";
    cout << v[i];
  }
  return cout << "]";
}
template <typename A, typename B>
istream& operator>>(istream& cin, pair<A, B>& p) {
  cin >> p.first;
  return cin >> p.second;
}
mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
void usaco(string filename) {
  freopen((filename + ".in").c_str(), "r", stdin);
  freopen((filename + ".out").c_str(), "w", stdout);
}
const long double pi = 3.14159265358979323846;
const long long mod = 1000000007;
template <typename num_t>
struct segtree {
  int n, depth;
  vector<num_t> tree, lazy;
  void init(int second, long long* arr) {
    n = second;
    tree = vector<num_t>(4 * second, 0);
    lazy = vector<num_t>(4 * second, 0);
    init(0, 0, n - 1, arr);
  }
  num_t init(int i, int l, int r, long long* arr) {
    if (l == r) return tree[i] = num_t(arr[l], l);
    int mid = (l + r) / 2;
    num_t a = init(2 * i + 1, l, mid, arr),
          b = init(2 * i + 2, mid + 1, r, arr);
    return tree[i] = a.op(b);
  }
  void update(int l, int r, num_t v) { update(0, 0, n - 1, l, r, v); }
  num_t update(int i, int tl, int tr, int ql, int qr, num_t v) {
    eval_lazy(i, tl, tr);
    if (ql <= tl && tr <= qr) {
      lazy[i] = lazy[i].val + v.val;
      eval_lazy(i, tl, tr);
      return tree[i];
    }
    if (tl > tr || tr < ql || qr < tl) return tree[i];
    if (tl == tr) return tree[i];
    int mid = (tl + tr) / 2;
    num_t a = update(2 * i + 1, tl, mid, ql, qr, v),
          b = update(2 * i + 2, mid + 1, tr, ql, qr, v);
    return tree[i] = a.op(b);
  }
  num_t query(int l, int r) { return query(0, 0, n - 1, l, r); }
  num_t query(int i, int tl, int tr, int ql, int qr) {
    eval_lazy(i, tl, tr);
    if (ql <= tl && tr <= qr) return tree[i];
    if (tl > tr || tr < ql || qr < tl) return num_t::null_v;
    int mid = (tl + tr) / 2;
    num_t a = query(2 * i + 1, tl, mid, ql, qr),
          b = query(2 * i + 2, mid + 1, tr, ql, qr);
    return a.op(b);
  }
  void eval_lazy(int i, int l, int r) {
    tree[i] = tree[i].lazy_op(lazy[i], (r - l + 1));
    if (l != r) {
      lazy[i * 2 + 1] = lazy[i].val + lazy[i * 2 + 1].val;
      lazy[i * 2 + 2] = lazy[i].val + lazy[i * 2 + 2].val;
    }
    lazy[i] = num_t();
  }
};
struct min_t {
  long long val;
  int ind;
  static const long long null_v = 9223372036854775807LL;
  min_t() : val(0) {}
  min_t(long long v) : val(v) {}
  min_t(long long v, int i) : val(v), ind(i){};
  min_t op(min_t& other) {
    if (other.val == val) return (ind > other.ind) ? other : *this;
    return (val > other.val) ? other : *this;
  }
  min_t lazy_op(min_t v, int size) { return min_t(val + v.val, ind); }
};
struct sum_t {
  long long val;
  int ind;
  static const long long null_v = 0;
  sum_t() : val(0) {}
  sum_t(long long v) : val(v) {}
  sum_t(long long v, int i) : val(v), ind(i){};
  sum_t op(sum_t& other) { return sum_t(val + other.val, ind); }
  sum_t lazy_op(sum_t v, int size) { return sum_t(val + v.val * size, ind); }
};
long long n, m, k, q, l, r, x, y, z;
const long long template_array_size = 1e6 + 1160;
long long a[template_array_size];
long long b[template_array_size];
long long c[template_array_size];
string second, t;
long long ans = 0;
pair<pair<long long, long long>, long long> qu[300005];
long long res[300005];
segtree<min_t> mt;
segtree<sum_t> st;
const long long inf = 1e9;
void toggle(long long i) {
  st.update(i, i, 1);
  mt.update(i, i, inf);
  if (i < n - 1) {
    mt.update(i + 1, n - 1, -1);
    min_t v;
    do {
      v = mt.query(i + 1, n - 1);
      if (v.val <= 0) {
        toggle(v.ind);
      }
    } while (v.val <= 0);
  }
}
void solve(int tc = 0) {
  cin >> n >> q;
  for (long long i = 0; i < n; i++) cin >> a[i];
  for (long long i = 0; i < n; i++) {
    --a[i];
    if (a[i] > i) {
      c[i] = inf;
    } else {
      c[i] = i - a[i];
    }
  }
  mt.init(n, c);
  for (long long i = 0; i < q; i++) {
    cin >> qu[i].first;
    qu[i].second = i;
  }
  sort(qu, qu + q);
  reverse(qu, qu + q);
  memset(b, 0, sizeof(b));
  st.init(n, b);
  long long rpt = n - 1;
  for (long long i = 0; i < q; i++) {
    while (rpt >= qu[i].first.first) {
      if (c[rpt] == 0) {
        toggle(rpt);
      }
      --rpt;
    }
    long long lb = qu[i].first.first, rb = n - qu[i].first.second - 1;
    res[qu[i].second] = st.query(lb, rb).val;
  }
  for (long long i = 0; i < q; i++) cout << res[i] << '\n';
}
int main() {
  { ios_base::sync_with_stdio(false); }
  {
    cin.tie(NULL);
    cout.tie(NULL);
  }
  int tc = 1;
  for (int t = 0; t < tc; t++) solve(t);
}
