给定一个长度为 $n$ 的序列 $a$，$q$ 次询问，每次询问一个区间 $[l,r]$ 的权值 $f(a_{l\sim r})$。

$f(A)$ 定义为：执行 $m$ 轮操作，非空的轮数。

具体的，令 $A$ 数组长度为 $m$，则执行 $m$ 轮操作。

第 $i$ 轮从 $i$ 开始，依次检查 $A_i$ 与 $A\_{i+1}\sim A_{m}$ 的大小关系，设当前检查 $A_i$ 与 $A_t$ 的大小关系，若 $A_i<A_t$ 则交换 $A_i$ 与 $A_t$，若第 $i$ 轮进行了至少一次交换，称这一轮非空。

具体的，以 $f([1,4,2,3])$ 为例，每一轮操作之后，数组分别为 $[4,1,2,3],[4,3,1,2],[4,3,2,1],[4,3,2,1]$，前 3 轮是非空的，所以 $f([1,4,2,3])=3$。

注意，f 函数对 原数组 $a$ 不造成任何实质上的影响，仅用于计算权值。

输入格式

第一行输入两个整数表示 n,q。 接下来一行输入 n 个整数表示 a 数组。 接下来输入 q 行，每行两个整数表示每次询问的区间。

输出格式

输出共 q 行，每行一个整数表示该组询问的答案。

样例输入 1

5 5
2 2 1 3 3
1 2
1 5 
2 4
2 5
1 4

样例输出 1

0
4
2
3
2

样例输入 2

10 10
4 10 4 8 2 3 3 10 6 8 
3 4
4 4
3 5
8 9
2 5
10 10
1 2
1 5
1 4
7 8

样例输出 2

1
0
1
0
1
0
1
2
2
1

样例 3

见 下发文件 。

数据范围与提示

对于所有的数据，满足 $1 \le n, q \le 10^6, 1 \le a_i \le n$。