P15130 [ROIR 2026] 超级跳跃

在电脑游戏《超级跳跃》中，英雄在山峰的顶点之间跳跃，目标是到达插有旗帜的位置，并在该处完成关卡。 游戏中的山脉由 $n$ 个连续排列的齿峰组成，第 $i$ 个齿峰位于位置 $i$，高度为 $h_i$。对于任意 $i < j$，英雄可以从齿峰 $i$ 沿直线跳跃到齿峰 $j$，条件是飞行路径上不会遇到其他齿峰。更正式地说，不存在这样的 $k$，使得 $i < k < j$ 且第 $k$ 个齿峰的顶点——坐标为 $(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, \ldots, 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$）—— 每个查询的参数。

对于每个查询，在单独的一行输出一个非负整数 —— 所需的最小跳跃次数。

### 样例解释 我们分析样例中给出的第二个查询。英雄从齿峰 2 到齿峰 7 的路径可以如下所示： :::align{center}  ::: 他将依次访问顶点 2、5 和 7，总共进行两次跳跃。 ### 评分规则 | 子任务 | 分值 | 额外限制 | 必要子任务 | |:-:|:-:|:-:|:-:| | 1 | 9 | $n, q \leq 300$ | | | 2 | 9 | $n, q \leq 5000$ | 1 | | 3 | 14 | $h_i \leq 10$ | | | 4 | 21 | 存在 $k$，使得对于所有 $i$，满足 $l_i \leq k \leq r_i$ | | | 5 | 27 | $n, q \leq 5 \cdot 10^4$ | 1, 2 | | 6 | 20 | 无额外限制 | 1–5 | 翻译由 DeepSeek 完成