题意： 给定一个正整数序列a1,…,an。你可以进行若干次操作，每次操作可以选择一个满足ai=i的位置i，将其删去。删去后，左右两边会自动拼合到一起（也就是右边所有数下标都会相应地变化）。

你想要最大化删去的元素数量。

但是这个问题太简单了，所以你需要回答q次询问。每次询问给定两个正整数x,y，求如果将序列的前x个数和后y个数变成n+1（也就是强制它们不得被删去），新的序列里最多能删掉多少个数呢？

注意，每次询问是独立的，也就是说询问后，序列会复原。

数据范围：1≤n,q≤3×105，1≤ai≤n，x,y≥0,x+y<n。

题解

先不考虑多次询问。只针对一个给定的序列，如何求答案呢？

我们发现，后面的数被删除时，不会对前面的数产生影响。因此，我们总能通过巧妙地安排删除顺序，使得所有“理论上能被删除的数”都被删掉。

例如，初始时的一个位置i，满足ai=i−2（也就是ai需要向前移动2格才能被删掉）。假设，我们已经知道了i前面有5个能被删除的数（即我们能构造出一种删除它们的方案）。那我们只要在这个方案进行到第2步时（此时ai向前移动了2格，满足了ai=i），把ai删掉。然后再继续删除后3个数即可。因为i的位置在它们后面，所以中间插入一个“删除ai”的操作，不会对原本的构造产生影响。于是我们就在“删除前i−1个数的方案”的基础上，构造出了“删除前i个数的方案”。用这种归纳，可以证明上一段所说的“应删尽删”的结论。

形式化地，我们设fi表示序列的前i个位置，最多有多少位置被删掉。则：

fi=fi−1+[i≥ai and fi−1≥i−ai]
如果没有多次询问，我们现在可以O(n)求出一个序列的答案。