区间递减
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

对于一个序列 a_1,a_2,a_3,..,a_n，我们定义如下操作(通过样例解释以更好理解)：
  • 原序列变为，从序列中删除一个元素后能得到的所有可能的序列中，字典序最小的序列

给定一个长度为 n 的序列 a_1,a_2,a_3,..,a_n。
现在凉刃老师对你进行 q 次询问，问你每次取出一段序列 b = [a_l,a_{l+1},..,a_{r}] 问最少需要在 b 序列上进行几次操作，才能使序列非递增。

概念解释
  • 对于两个长度都为 n 的序列 a,b，序列 a 字典序小于序列 b \iff \exists i \in [1,n], a_i < b_i \cap \forall 1 \le j<i, a_j = b_j
  • 称长度为 n 的序列 a 非递增 \iff \forall i \in [1,n-1], a_i \ge a_{i+1}

输入描述:

第一行两个整数 n,q（1 \le n,q \le 2\times 10^5），以空格分隔，分别表示数组长度和询问次数。

第二行 n 个正整数 a_1,a_2,a_3,..,a_n（1 \le a_i \le 10^9），以空格分隔。

接下来 q 行，每行两个整数 l,r（1 \le l \le r \le n）, 以空格分隔，表示一次询问。

输出描述:

输出 q 行，每行一个非负整数，分别表示每次询问的答案。
示例1

输入

复制 
5 2
1 4 2 3 5
2 5
2 3

输出

复制 
3
0

说明

对于第一个询问：

- 第一次操作：[4, 2, 3, 5] 删除一个元素后可能的序列为 [2, 3, 5], [4, 3, 5], [4, 2, 5], [4, 2, 3]，其中字典序最小的为 [2, 3, 5]；
- 第二次操作：[2, 3, 5] 删除一个元素后可能的序列为 [3, 5], [2, 5], [2, 3]，其中字典序最小的为 [2, 3]；
- 第三次操作：[2, 3] 删除一个元素后可能的序列为 [2], [3]，其中字典序最小的为 [2]；

总共需要 3 次操作。

对于第二个询问序列 [4,2]，初始就是非递增，不需要操作。

备注: