P14387 [JOISC 2017] 火车旅行 / Railway Trip

JOI 铁路公司运营一条铁路。在 JOI 铁路的线路上，有 $N$ 个车站沿直线排列，编号从 $1$ 到 $N$。对于每个 $i$（$1 \le i \le N - 1$），车站 $i$ 与车站 $i + 1$ 由一条铁轨连接。 JOI 铁路公司运营 $K$ 种类型的列车，每种列车均双向运行。列车类型用 $1$ 到 $K$（含）之间的整数表示。每个车站有一个“等级”，也是一个 $1$ 到 $K$（含）之间的整数。对于每个 $i$（$1 \le i \le N$），车站 $i$ 的等级为 $L_i$。两端的车站，即车站 $1$ 和车站 $N$，等级均为 $K$。 类型为 $j$（$1 \le j \le K$）的列车会在所有等级大于等于 $j$ 的车站停靠，且不在其他任何车站停靠。由于两端的车站（即车站 $1$ 和车站 $N$）等级均为 $K$，因此所有列车均在这两个车站停靠。 每天都有许多乘客使用 JOI 铁路。在旅途中，他们可以乘坐方向与目的地相反的列车，或者直接经过目的地。但在旅行结束时，他们必须在目的地车站下车。他们不喜欢在车站过多停靠，因此会尽量选择中间停靠站数量最少的路线，而不论经过的车站总数或换乘次数。若乘客在某个车站下车换乘，我们将其计为一次停靠。起点站的首次停靠和终点站的最后一次停靠不计入中间停靠站。 你的任务是编写一个程序，能够回答每位乘客的最小中间停靠站数量的查询。 **任务** 给定 JOI 铁路的信息，以及每位乘客的起始站和目的地，编写一个程序，能够回答每位乘客的最小中间停靠站数量的查询。

从标准输入读取以下数据： - 输入的第一行包含三个以空格分隔的整数 $N$、$K$、$Q$。这表示 JOI 铁路有 $N$ 个车站，有 $K$ 种类型的列车，并给出 $Q$ 个关于两站之间旅行的查询。 - 接下来的 $N$ 行中，第 $i$ 行（$1 \le i \le N$）包含一个整数 $L_i$，表示车站 $i$ 的等级。 - 接下来的 $Q$ 行中，第 $k$ 行（$1 \le k \le Q$）包含两个以空格分隔的整数 $A_i$、$B_i$。这表示第 $k$ 位乘客的起始站和目的地分别为车站 $A_i$ 和 $B_i$。

向标准输出写入 $Q$ 行。第 $k$ 行（$1 \le k \le Q$）包含从车站 $A_k$ 到车站 $B_k$ 的路线中最小的中间停靠站数量。

### 样例 1 解释 在本样例输入中，给出了三个关于两站之间旅行的查询： - 第一个查询是关于从车站 2 到车站 4 的旅行。若乘客乘坐类型为 1 的列车从车站 2 直达车站 4，则仅有一个中间停靠站，即车站 3。 - 第二个查询是关于从车站 4 到车站 9 的旅行。若乘客先乘坐类型为 1 的列车从车站 4 到车站 5，再乘坐类型为 2 的列车从车站 5 到车站 1，最后乘坐类型为 3 的列车从车站 1 到车站 9，则共有三个中间停靠站，分别为车站 5、1 和 8。 - 第三个查询是关于从车站 6 到车站 7 的旅行。若乘客乘坐类型为 2 的列车从车站 6 直达车站 7，则无中间停靠站。 ### 样例 2 解释 请注意，乘客在旅途中可以经过目的地车站。 ### 数据范围 所有输入数据均满足以下条件： - $2 \le N \le 100\,000$。 - $1 \le K \le N$。 - $1 \le Q \le 100\,000$。 - $1 \le L_i \le K$（$1 \le i \le N$）。 - $1 \le A_k \le N$（$1 \le k \le Q$）。 - $1 \le B_k \le N$（$1 \le k \le Q$）。 - $A_k \ne B_k$（$1 \le k \le Q$）。 ### 子任务 共有 4 个子任务。每个子任务的得分及额外约束如下： **子任务 1 [5 分]** - $N \le 100$。 - $K \le 100$。 - $Q \le 50$。 **子任务 2 [15 分]** - $Q \le 50$。 **子任务 3 [25 分]** - $K \le 20$。 **子任务 4 [55 分]** 无额外约束。 翻译由 Qwen3-235B 完成