JOI Railways 是一家运营一条铁路线的公司。在 JOI Railways 的铁路上，有 $N$ 个车站，它们在一条直线上，编号从 $1$ 到 $N$。对于每个 $i$ ($1 \le i \le N - 1$)，车站 $i$ 和车站 $i + 1$ 之间由一段铁轨连接。

JOI Railways 有 $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 Railways。在旅行过程中，他们可以乘坐与目的地方向相反的列车，也可以经过目的地。旅行结束时，他们必须在目的地车站下车。乘客不喜欢频繁停靠。因此，他们试图寻找一条中间停靠次数最少的路线，而不考虑经过的车站数量或换乘次数。如果乘客在某个车站换乘列车，我们将其计为一次停靠。出发站的首次停靠和目的地车站的最后停靠不计为中间停靠。

你的任务是编写一个程序，回答每位乘客关于最少中间停靠次数的查询。

输入格式

从标准输入读取以下数据。

• 第一行包含三个空格分隔的整数 $N, K, Q$。这表示 JOI Railways 有 $N$ 个车站，$K$ 种类型的列车，以及 $Q$ 个关于两站之间旅行的查询。
• 接下来的 $N$ 行中，第 $i$ 行 ($1 \le i \le N$) 包含一个整数 $L_i$，表示车站 $i$ 的等级。
• 接下来的 $Q$ 行中，第 $k$ 行 ($1 \le k \le Q$) 包含两个空格分隔的整数 $A_k, B_k$。这表示第 $k$ 位乘客的出发站和目的地分别是车站 $A_k$ 和 $B_k$。

输出格式

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

数据范围

所有输入数据满足以下条件：

• $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 \neq 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 分] * 无附加限制。

样例

样例输入 1

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

样例输出 1

1
3
0

说明

在此样例输入中，给出了三个关于两站之间旅行的查询。

• 第一个查询是关于从车站 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

5 2 1
2
1
1
1
2
1 4

样例输出 2

1

注意，乘客在旅行过程中可以经过目的地。

样例输入 3

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

样例输出 3

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