给定一个长度为 $ 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 $。