序列

题目描述

给定一个含有 $n$ 个正整数的序列 $a$ ，对于一次操作，你可以任选一个位置 $i$ 且满足 $a_i=i$ ,那么就可以移除这个元素，并将后面所有的元素向前移动一位。

对于每个相互独立的询问 $x,y$ 需要你求出在前 $x$ 个元素以及后 $y$ 个元素不能被移除的情况下，最多可以进行几次操作。

输入格式

第一行两个正整数 $n,q$，表示初始序列长度和询问次数。

接下来一行 $n$ 个正整数描述了初始序列 $a$。

接下来 $q$ 行，每行两个正整数 $x,y$，表示一次询问，含义如题意所述。

输出格式

对于每次询问，输出对应的最多操作次数。

样例

Input 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

Output 1

5
11
6
1
0

Input 2

5 2
1 4 1 2 4
0 0
1 0

Output 2

2
0

提示说明

Constraints

$0 \le x,y$ 且 $x+y\le n$