Fixed Point Removal

题意翻译

给定一个含有 $n$ 个正整数的序列 $a$ ，对于一次操作，你可以任选一个位置 $i$ 且满足 $a_i=i$ ,那么就可以移除这个元素，并将后面所有的元素向前移动一位。 对于每个相互独立的询问 $x,y$ 需要你求出在前 $x$ 个元素以及后 $y$ 个元素不能被移除的情况下，最多可以进行几次操作。 $n,q \leq 3\times 10^5$ translated by [lory1608](https://www.luogu.com.cn/user/333789#practice)

题目描述

Let $ a_1, \ldots, 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 $ ?

输入输出格式

输入格式

The first line contains two integers $ n $ and $ q $ ( $ 1 \le n, q \le 3 \cdot 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 \leq a_i \leq n $ ) — elements of the array. The $ i $ -th of the next $ q $ lines contains two integers $ x $ and $ y $ ( $ x, y \ge 0 $ and $ x+y < n $ ).

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

5
11
6
1
0

输入样例 #2

5 2
1 4 1 2 4
0 0
1 0

输出样例 #2

2
0

说明

Explanation of the first query: After making first $ x = 3 $ and last $ y = 1 $ elements impossible to remove, $ a $ becomes $ [\times, \times, \times, 9, 5, 4, 6, 5, 7, 8, 3, 11, \times] $ (we represent $ 14 $ as $ \times $ for clarity). Here is a strategy that removes $ 5 $ elements (the element removed is colored in red): - $ [\times, \times, \times, 9, \color{red}{5}, 4, 6, 5, 7, 8, 3, 11, \times] $ - $ [\times, \times, \times, 9, 4, 6, 5, 7, 8, 3, \color{red}{11}, \times] $ - $ [\times, \times, \times, 9, 4, \color{red}{6}, 5, 7, 8, 3, \times] $ - $ [\times, \times, \times, 9, 4, 5, 7, \color{red}{8}, 3, \times] $ - $ [\times, \times, \times, 9, 4, 5, \color{red}{7}, 3, \times] $ - $ [\times, \times, \times, 9, 4, 5, 3, \times] $ (final state) It is impossible to remove more than $ 5 $ elements, hence the weight is $ 5 $ .

题意翻译

给定一个含有 $n$ 个正整数的序列 $a$ ，对于一次操作，你可以任选一个位置 $i$ 且满足 $a_i=i$ ,那么就可以移除这个元素，并将后面所有的元素向前移动一位。 对于每个相互独立的询问 $x,y$ 需要你求出在前 $x$ 个元素以及后 $y$ 个元素不能被移除的情况下，最多可以进行几次操作。 $n,q \leq 3\times 10^5$ translated by [lory1608](https://www.luogu.com.cn/user/333789#practice)