logo AlgoBeat OnlineJudge
登录 注册

#215263. [ROIR 2026] 超级跳跃

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

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

游戏中的山脉由 个连续排列的齿峰组成,第 个齿峰位于位置 ,高度为 。对于任意 ,英雄可以从齿峰 沿直线跳跃到齿峰 ,条件是飞行路径上不会遇到其他齿峰。更正式地说,不存在这样的 ,使得 且第 个齿峰的顶点——坐标为 的点——严格高于连接点 的线段。

“战胜 AI”公司正在训练一个神经网络来控制游戏中的英雄。为了创建训练数据,需要回答多个查询:对于一对索引 ),确定从编号为 的齿峰开始,英雄到达编号为 的齿峰所需的最小跳跃次数。

输入格式

输入数据的第一行包含一个数字 )—— 齿峰的数量。

第二行包含 个数字:)—— 齿峰的高度。

第三行包含一个数字 )—— 查询的数量。

接下来的 行中,每行包含两个数字 )—— 每个查询的参数。

输出格式

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

样例

样例输入 1

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

样例输出 1

2
2
0

数据范围与提示

样例解释

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

:::align{center} :::

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

评分规则

子任务 分值 额外限制 必要子任务
1 9
2 1
3 14
4 21 存在 ,使得对于所有 ,满足
5 27 1, 2
6 20 无额外限制 1–5

翻译由 DeepSeek 完成