AT_joisc2017_f.鉄道旅行 (Railway Trip)

JOI 铁路公司是一家运营一条铁路线路的企业。在该公司的这条铁路线上，有 $N$ 座车站沿直线分布，编号从 $1$ 到 $N$。对于每一个 $i$（$1\leq i \leq N − 1$），车站 $i$ 和车站 $i + 1$ 之间均通过一段铁轨相连。

JOI 铁路公司运营着 $K$ 种双向行驶的列车，列车类型用 $1$ 到 $K$（包含 $1$ 和 $K$）之间的整数表示。每座车站都有一个等级，等级为 $1$ 到 $K$（包含 $1$ 和 $K$）之间的整数。对于每一个 $i$（$1\leq i\leq N$），车站 $i$ 的等级记为 $L_i$。线路两端的车站，即车站 $1$ 和车站 $N$，等级均为 $K$。

类型为 $j$（$1\leq j\leq K$）的列车会在所有等级大于或等于 $j$ 的车站停靠，而不会在其他等级的车站停靠。由于线路两端的车站（车站 $1$ 和车站 $N$）等级均为 $K$，因此所有类型的列车都会在这两座车站停靠。

每天都有大量乘客乘坐 JOI 铁路公司的列车出行。在行程中，乘客可以乘坐与目的地方向相反的列车，也可以经过目的地（不停靠），但行程结束时，必须在目的地车站停靠。乘客不太喜欢在中途车站停靠，因此他们会选择中途停靠次数最少的路线，而不考虑经过的车站数量或换乘次数。需要注意的是，如果乘客在某座车站停靠以换乘列车，该次停靠会被计入中途停靠次数；而行程开始时在出发站的停靠，以及行程结束时在目的地的停靠，均不计入中途停靠次数。

你的任务是编写一个程序，针对每位乘客的查询，计算出其行程所需的最少中途停靠次数。

从标准输入中读取以下数据：

• 输入的第一行包含三个用空格分隔的整数 $N,K,Q$，分别表示 JOI 铁路公司的车站总数为 $N$，列车类型总数为 $K$，以及关于两站之间行程的查询数量为 $Q$。
• 接下来的 $N$ 行中，第 $i$ 行（$1 \leq i \leq N$）包含一个整数 $L_i$，表示车站 $i$ 的等级。
• 再接下来的 $Q$ 行中，第 $k$ 行（$1 \leq k \leq Q$）包含两个用空格分隔的整数 $A_k,B_k$，分别表示第k位乘客的出发站为车站 $A_k$，目的地为车站 $B_k$。

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

对于所有数据，$2\le N\le 10^5, 1\le K\le N, 1\le Q\le 10^5, 1\le L_i\le K(1\le i\le N), 1\le A_k, B_k\le N, A_k\not=B_k(1\le k\le Q)$。