题目描述

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$ 的路线中最小的中间停靠站数量。

9 3 3
3
1
1
1
2
2
2
3
3
2 4
4 9
6 7

1
3
0

5 2 1
2
1
1
1
2
1 4

1

15 5 15
5
4
1
2
3
1
1
2
4
5
4
1
5
3
5
8 1
11 1
5 3
6 11
9 12
15 14
15 2
3 12
2 1
4 8
15 5
12 6
1 13
13 8
14 9

2
1
1
3
2
0
3
4
0
1
3
4
1
2
2

提示

样例 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 完成