题目描述

在苏门答腊岛的热带雨林中，有 $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$。

每个测试点的具体限制见下表：

大样例