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$ 的旅程。如果乘客搭乘種類 $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