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。旅途中，佢哋可以搭同目的地方向相反嘅列車，亦可以經過目的地而唔停站。旅程結束時，佢哋必須喺目的地停站。佢哋唔太鍾意停站，所以會盡量揀中途停站次數最少嘅路線，而唔理經過幾多個車站或者轉幾多次車。如果乘客喺一個車站停低轉車，就計作一次停站。起點嘅首次停站同目的地嘅最後一次停站，都唔計作中途停站。

你嘅任務係寫一個程式，回答每位乘客最少中途停站次數嘅查詢。

任務

畀定 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_i,B_i$。呢個表示第 $k$ 位乘客嘅起點車站同目的地分別係車站 $A_i,B_i$。

輸出格式

向標準輸出寫出 $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 \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 分]

冇額外限制。

樣例

輸入格式 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$ 嘅旅程。如果乘客由車站 $2$ 搭第 $1$ 種列車去車站 $4$，就只會有一次中途停站，即車站 $3$。
• 第二個查詢係由車站 $4$ 去車站 $9$ 嘅旅程。如果乘客先由車站 $4$ 搭第 $1$ 種列車去車站 $5$，再由車站 $5$ 搭第 $2$ 種列車去車站 $1$，最後由車站 $1$ 搭第 $3$ 種列車去車站 $9$，就會有三次中途停站，分別係車站 $5,1,8$。
• 第三個查詢係由車站 $6$ 去車站 $7$ 嘅旅程。如果乘客由車站 $6$ 搭第 $2$ 種列車去車站 $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