4406: 「JOISC 2017 Day 2」火车旅行

**题目译自 [JOISC 2017](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/index.html) Day2 T3「[鉄道旅行](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d2.pdf) / [Railway Trip](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d2-en.pdf)」** 某条铁路线（非环线）有 $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 N)$ 有两个整数 $A_k,B_k$。

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

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

1
3
0