← 返回题目列表

Codeforces · 1922/C

C. 最近的城市

中文机器翻译题面 查看原题

数轴上有 $$$n$$$ 个城市,第 $$$i$$$ 个城市在点 $$$a_i$$$ 上。城市坐标按升序给出,因此 $$$a_1 < a_2 < \dots < a_n$$$。

两个城市 $$$x$$$ 和 $$$y$$$ 之间的距离等于 $$$|a_x - a_y|$$$。

对于每个城市 $$$i$$$,我们将最近的城市 $$$j$$$ 定义为使得 $$$i$$$ 和 $$$j$$$ 之间的距离不大于 $$$i$$$ 和每个其他城市 $$$k$$$ 之间的距离的城市。例如,如果城市位于点 $$$[0, 8, 12, 15, 20]$$$,则:

- 距离城市$$$1$$$最近的城市是城市$$$2$$$;
- 距离城市$$$2$$$最近的城市是城市$$$3$$$;
- 距离城市$$$3$$$最近的城市是城市$$$4$$$;
- 距离城市$$$4$$$最近的城市是城市$$$3$$$;
- 距离城市 $$$5$$$ 最近的城市是城市 $$$4$$$。

城市的定位方式使得对于每个城市来说,最近的城市都是唯一的。例如,城市不可能位于点 $$$[1, 2, 3]$$$ 中,因为这意味着城市 $$$2$$$ 有两个最近的城市($$$1$$$ 和 $$$3$$$,两者的距离为 $$$1$$$)。

您可以在城市之间旅行。假设您目前在城市 $$$x$$$。然后您可以执行以下操作之一:

- 前往任何其他城市 $$$y$$$,支付 $$$|a_x - a_y|$$$ 硬币;
- 前往距离$$$x$$$最近的城市,支付$$$1$$$硬币。

您收到了 $$$m$$$ 查询。在每个查询中,您将获得两个城市,您必须计算从一个城市到另一城市所需花费的最少硬币数量。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例均按以下格式给出:

- 第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$);
- 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_1 < a_2 < \dots < a_n \le 10^9$$$);
- 第三行包含一个整数 $$$m$$$ ($$$1 \le m \le 10^5$$$);
- 然后是 $$$m$$$ 行;其中第 $$$i$$$ 包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$),表示在第 $$$i$$$ 查询中,你必须计算从城市出发需要花费的最少硬币数量$$$x_i$$$ 到城市$$$y_i$$$。

输入的附加限制:

- 在每个测试用例中,对于每个城市,最近的城市是唯一确定的;
- 所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$;
- 所有测试用例的 $$$m$$$ 总和不超过 $$$10^5$$$。

输出

对于每个查询,打印一个整数 - 您必须花费的最少硬币数量。

示例

输入 #1

1
5
0 8 12 15 20
5
1 4
1 5
3 4
3 2
5 1

输出 #1

3
8
1
4
14

注意

让我们考虑一下该语句中示例中的前两个查询:

- 在第一个查询中,您最初位于城市 $$$1$$$。您可以支付 $$$1$$$ 硬币前往最近的城市(即 $$$2$$$ 的城市)。然后你再次前往最近的城市(即城市 $$$3$$$),支付 $$$1$$$ 硬币。然后你再次前往最近的城市(即城市 $$$4$$$),支付 $$$1$$$ 硬币。总共,您花费 $$$3$$$ 硬币从城市 $$$1$$$ 到城市 $$$4$$$;
- 在第二个查询中,您可以使用相同的方式从城市$$$1$$$前往城市$$$4$$$,然后花费$$$5$$$金币从城市$$$4$$$前往城市$$$5$$$。