题目链接
Let $a_1,\dots,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$.

按照贪心原则，首先如果每次取最后一个满足条件的，结果一定最优。因为每次取最后满足条件的不会使得当前满足条件的其他项变得不满足条件，结果一定不会更差。
如果第$i$个位置可以选择，那么可能会造成$[i+1,n]$中没有删掉的数出现满足条件的，因此每次询问的左端点$l$不同，区间$[l,n]$中可以删掉的数也不同，因此对于每个左端点$l$都要保存一个历史版本，记录$[l,n]$中可以删掉的数。这样，对于$[l,r]$的询问，只需要输出版本$l$的区间$[l,r]$中可以删掉的数的数量即可。可以用主席树维护。
要构造这样一棵主席树，需要对贪心操作进行模拟。具体模拟过程是利用线段树维护，维护的区间上位置$i$的值为$i-a[i]$，然后线段树支持区间修改和区间最小值及其位置的查询，最小值应优先选右边的，从右向左扫描序列$a$，如果$a[i]=i$，则询问$[i,n]$的最小值，如果最小值小于$0$，则不可能被选到，设为$\infin$，继续询问；如果最小值等于$0$，则该位置满足条件，且位置为$pos$，修改主席树，将该值设为$\infin$，因为剩下的数左移，因此将区间$[pos,n]$减$1$；如果最小值大于$0$，则目前没有满足条件的，跳出循环。
时间复杂度为$O(n\log n)$。

#include<bits/stdc++.h>#define pi(a) printf("%d\n",a)
#define repi(i, a, b) for(register int i=a;i<=b;++i)
#define pii pair<int,int>
#define fi first
#define se second
#define INF 0x3f3f3f3f
using namespace std;inline int qr() {int f = 0, fu = 1;char c = getchar();while (c < '0' || c > '9') {if (c == '-')fu = -1;c = getchar();}while (c >= '0' && c <= '9') {f = (f << 3) + (f << 1) + c - 48;c = getchar();}return f * fu;
}const int N = 3e5 + 10;struct Seg_Tree {struct {int l, r, ans, add, pos;} t[N * 4];inline void update(int p) {if (t[p << 1].ans < t[p << 1 | 1].ans)t[p].ans = t[p << 1].ans, t[p].pos = t[p << 1].pos;else t[p].ans = t[p << 1 | 1].ans, t[p].pos = t[p << 1 | 1].pos;}void build(int p, int l, int r, int *a) {t[p].l = l, t[p].r = r, t[p].add = 0;if (l == r)return t[p].ans = a[l], t[p].pos = l, void();int mid = (l + r) >> 1;build(p << 1, l, mid, a), build(p << 1 | 1, mid + 1, r, a);update(p);}inline void spread(int p) {if (t[p].add) {t[p << 1].ans += t[p].add, t[p << 1 | 1].ans += t[p].add;t[p << 1].add += t[p].add, t[p << 1 | 1].add += t[p].add;t[p].add = 0;}}void change(int p, int l, int r, int c) {if (l <= t[p].l && t[p].r <= r) {t[p].add += c, t[p].ans += c;return;}spread(p);int mid = (t[p].l + t[p].r) >> 1;if (l <= mid)change(p << 1, l, r, c);if (r > mid)change(p << 1 | 1, l, r, c);update(p);}pii ask(int p, int l, int r) {if (l <= t[p].l && r >= t[p].r)return {t[p].ans, t[p].pos};spread(p);int mid = (t[p].l + t[p].r) >> 1;pii val = {INF, 0};if (r > mid)val = ask(p << 1 | 1, l, r);if (l <= mid) {pii res = ask(p << 1, l, r);if (res.fi < val.fi)val = res;}return val;}
} S;struct CMT {int seq[N], rt[N], tot;struct {int l, r, val;} t[N << 5];int update(int p, int l, int r, int x, int v) {int dir = ++tot;t[dir] = t[p];if (l == r) {t[dir].val += v;return dir;}int mid = (l + r) >> 1;if (x <= mid)t[dir].l = update(t[dir].l, l, mid, x, v);else t[dir].r = update(t[dir].r, mid + 1, r, x, v);t[dir].val = t[t[dir].l].val + t[t[dir].r].val;return dir;}int ask(int p, int l, int r, int x, int y) {if (x <= l && y >= r)return t[p].val;int mid = (l + r) >> 1;int val = 0;if (x <= mid)val = ask(t[p].l, l, mid, x, y);if (y > mid)val += ask(t[p].r, mid + 1, r, x, y);return val;}
} C;int n, q, a[N];int main() {n = qr(), q = qr();repi(i, 1, n)a[i] = i - qr();S.build(1, 1, n, a);int now = n;while (now >= 1) {while (a[now]) C.rt[now] = C.rt[now + 1], now--;C.rt[now] = C.rt[now + 1];while (true) {pii res = S.ask(1, now, n);if (res.fi < 0) {S.change(1, res.se, res.se, INF);continue;} else if (res.fi == 0) {C.rt[now] = C.update(C.rt[now], 1, n, res.se, 1);S.change(1, min(n, res.se + 1), n, -1);S.change(1, res.se, res.se, INF);continue;}now--;break;}}while (q--) {int x = qr() + 1, y = n - qr();pi(C.ask(C.rt[x], 1, n, x, y));}return 0;
}