CF1922C Closest Cities

有 $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$，你可以执行以下操作之一： - 以 $|a_x - a_y|$ 个金币的代价，前往任意其他城市 $y$； - 以 $1$ 个金币的代价，前往距离 $x$ 最近的城市。 现在给定 $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$ 行，每行包含两个整数 $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$。你可以依次前往最近的城市（城市 $2$），花费 $1$ 个金币，再前往最近的城市（城市 $3$），再花费 $1$ 个金币，再前往最近的城市（城市 $4$），再花费 $1$ 个金币。总共花费 $3$ 个金币，从城市 $1$ 到城市 $4$。 - 第二个询问，你可以用同样的方法从城市 $1$ 到城市 $4$，然后再花费 $5$ 个金币从城市 $4$ 到城市 $5$。 由 ChatGPT 4.1 翻译