[AdditionalFile5567.zip](file://AdditionalFile5567.zip?type=additional_file)

#5567. 「ROIR 2026 Day1」山峰跳跃

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

译自 ROI Regional 2026 Day1 T4. Прыжки по вершинам

在电脑游戏《超级跳跃》中，英雄需要在山脉的峰顶之间跳跃，目标是到达带有旗帜的终点峰顶，完成关卡。

山脉由 $n$ 个连续的峰顶组成，第 $i$ 个峰顶位于位置 $i$，高度为 $h_i$。英雄可以从第 $i$ 个峰顶直接跳到第 $j$ 个峰顶 $(i < j)$，条件是：在直线飞行路径上，没有其他峰顶严格高于连接 $(i, h_i)$ 和 $(j, h_j)$ 的线段。更正式地说：不存在 $k$ $(i < k < j)$，使得点 $(k, h_k)$ 严格位于线段 $(i, h_i)$-$(j, h_j)$ 的上方。

「击败AI」公司正在训练神经网络来控制游戏中的英雄。为了生成训练数据，需要回答多个询问：对于给定的左右端点 $l, r$ $(1 \leq l \leq r \leq n)$，计算从峰顶 $l$ 出发，到达峰顶 $r$ 所需的最少跳跃次数。

输入格式

第一行一个整数 $n$ $(1 \leq n \leq 10^5)$，表示峰顶数量。

第二行 $n$ 个整数 $h_1, h_2, \dots, h_n$ $(0 \leq h_i \leq 10^{12})$，表示各峰顶高度。

第三行一个整数 $q$ $(1 \leq q \leq 10^5)$，表示询问数量。

接下来 $q$ 行，每行两个整数 $l_i, r_i$ $(1 \leq l_i \leq r_i \leq n)$，表示一次询问的参数。

输出格式

对每个询问输出一行一个非负整数，表示从 $l_i$ 到达 $r_i$ 所需的最少跳跃次数。

样例

输入

8
5 3 4 3 6 2 1 4
3
1 8
2 7
4 4

输出

2
2
0

样例中的第二个询问（从峰顶 $2$ 到峰顶 $7$）：

英雄可以访问峰顶 $2 \to 5 \to 7$，共进行 $2$ 次跳跃。

数据范围与提示

详细子任务附加限制及分值如下表所示：