题目描述

在电脑游戏《超级跳跃》中，英雄在山峰的顶点之间跳跃，目标是到达插有旗帜的位置，并在该处完成关卡。

游戏中的山脉由 $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$）—— 每个查询的参数。

输出格式

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

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

2
2
0

提示

样例解释

我们分析样例中给出的第二个查询。英雄从齿峰 2 到齿峰 7 的路径可以如下所示：

:::align{center} :::

他将依次访问顶点 2、5 和 7，总共进行两次跳跃。

评分规则

翻译由 DeepSeek 完成