给定一个长度为 $ 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 $。
| 测试点编号 | $ n,q $ | 是否 $ a $ 形如排列 |
|---|---|---|
| $ 1\sim 1 $ | $ \le 100 $ | 是 |
| $ 2\sim 2 $ | $ \le 100 $ | 否 |
| $ 3\sim 5 $ | $ \le 3000 $ | 是 |
| $ 6\sim 8 $ | $ \le 3000 $ | 否 |
| $ 9\sim 10 $ | $ \le 10000 $ | 是 |
| $ 11\sim 12 $ | $ \le 10000 $ | 否 |
| $ 13\sim 13 $ | $ \le 200000 $ | 是 |
| $ 14\sim 16 $ | $ \le 200000 $ | 否 |
| $ 17\sim 17 $ | $ \le 1000000 $ | 是 |
| $ 18\sim 20 $ | $ \le 1000000 $ | 否 |