题目描述
在苏门答腊岛的热带雨林中，有 $n$ 棵树排成一排，从左到右依次用 $1$ 到 $n$ 进行编号，其中 $i$ 号树的高度为 $h_i$。
Pak Dengklek 正在训练一只猩猩，让它能够从一棵树跳到另一棵树上。对于一次跳跃，猩猩可以从一棵树，向左或向右跳到高度不低于当前这棵树的第一棵树上，且不能越过高度严格小于起点的树。这只猩猩不会改变自己的方向，也就是它只会一直向左跳或一直向右跳。
Pak Dengklek 有 $q$ 个训练计划，每个计划用两个整数 $1 ≤ l ≤ r ≤ n$ 来描述。对于每个计划，Pak Dengklek 想知道猩猩在只经过编号在 $[l, r]$ 中的树时至多能越过多少棵树。猩猩可以从 $[l, r]$ 中任意一棵树出发。如果猩猩从第 $x$ 棵树最终跳到了第 $y$ 棵树，则它越过了 $|x − y| + 1$ 棵树。
输入格式
第一行两个整数 $n, q$。
第二行 $n$ 个整数 $h_{1\cdots n}$。
接下来 $q$ 行，每行两个整数 $l, r$ 描述一个训练计划。
输出格式
共 $q$ 行，第 $i$ 行一个整数表示第 $i$ 个训练计划中猩猩至多能越过多少棵树。
样例 1 输入
7 3
3 2 1 6 4 5 7
5 7
4 7
2 5样例 1 输出
3
3
2样例 1 解释
对于询问 $[5, 7]$，猩猩可以从 $5$ 跳到 $6$ 再跳到 $7$，因为 $h_5 ≤ h_6 ≤ h_7$。
对于询问 $[2, 5]$，猩猩可以从 $3$ 跳到 $4$，因为 $h_3 ≤ h_4$，但不能再从 $4$ 跳到 $5$。
样例 2、3
见 /ex_jump2.in、/ex_jump3.in 与 /ex_jump2.out、/ex_jump3.out。 样例 2 满足测试点 2 ∼ 3 的限制以及特殊限制。 样例 3 满足测试点 4 ∼ 6 的限制。
测试点约束
对于所有测试点，$1 ≤ n, q ≤ 5 × 10^5，1 ≤ hi ≤ 10^9，1 ≤ l ≤ r ≤ n$。
每个测试点的具体限制见下表：
| 测试点编号 | $n\le$ | $q\le$ | 特殊限制 |
|---|---|---|---|
| 1 | $100$ | $100$ | |
| 2-3 | $5\times10^3$ | $5\times10^3$ | |
| 4-6 | $3\times10^4$ | $3\times10^4$ | |
| 7-8 | $5\times10^5$ | $5\times10^5$ | $h_i\le20$ |
| 9-10 | $5\times10^5$ | $5\times10^5$ |