2395 「JOISC 2017 Day 2」火车旅行

题目译自 JOISC 2017 Day2 T3「鉄道旅行 / Railway Trip」

某条铁路线（非环线）有 $N$ 站，依次编号为 $1\ldots N$。这条线路上跑着 $K$ 类列车，编号为 $1\ldots K$。每种列车都是双向运行的。
这条铁路线上的每个车站都有个旅客流量，旅客流量是一个 $\le K$ 的正整数。车站 $i(1\le i\le N)$ 的旅客流量为 $L_i$，$L_1=L_N=K$。
第 $j$ 类列车 $(1\le j\le K)$ 在且只在旅客流量 $\ge j$ 的车站停车。 现有 $Q$ 名旅客，依次编号为 $1\ldots Q$，旅客 $k(1\le k\le Q)$ 的起点是车站 $A_k$，终点是 $B_k$ $(1\le A_k, B_k\le N)$。假设这些旅客只能靠这条铁路线移动。
对于每个旅客，求这名旅客的途中至少要停几次站（不含该旅客的起终点站）。保证同一名旅客的起点与终点不同。允许走回头路。

第一行有三个整数 $N, K, Q$，用空格分隔。
在接下来的 $N$ 行中，第 $i$ 行 $(1\le i\le N)$ 有一个整数 $L_i$。
在接下来的 $Q$ 行中，第 $k$ 行 $(1\le k\le Q)$ 有两个整数 $A_k,B_k$。

输出共 $Q$ 行，每行一个整数，表示旅客 $k$ 最少的停站次数。

旅客 $1$ 从车站 $2$ 出发，可以直接坐 $1$ 类车抵达车站 $4$。中途站只有车站 $3$。 旅客 $2$ 从车站 $4$ 出发，可以先坐 $1$ 类车到车站 $5$，再换乘 $2$ 类车坐到车站 $1$，再换乘 $3$ 类车坐到车站 $9$。中途站为车站 $5,1,8$。 旅客 $3$ 从车站 $6$ 出发，直接坐 $1$ 类车抵达车站 $7$。

注意可以走过目的地，再走回来。