기차 여행

JOI 철도는 철도 노선 하나를 운영하는 회사이다. 이 철도는 직선 위에 놓인 N개의 역으로 이루어져 있고, 역에는 1번부터 N번까지 번호가 붙어 있다. 각 $i$ ($1 \le i \le N-1$)에 대해 $i$번 역과 $i+1$번 역은 선로로 연결되어 있다.

JOI 철도에는 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이므로 모든 열차가 이 두 역에 선다.

많은 승객이 매일 이 철도를 이용한다. 이동 중에 승객은 목적지와 반대 방향으로 가는 열차를 탈 수도 있고, 목적지를 지나칠 수도 있다. 여행의 마지막에는 목적지에서 반드시 내려야 한다. 승객은 역에 서는 것을 싫어하므로, 지나치는 역의 수나 열차를 갈아타는 횟수와 관계없이 중간 정차 횟수가 가장 적은 경로를 택한다. 환승을 위해 역에 정차하면 정차 1회로 센다. 출발역에서의 첫 정차와 목적지에서의 마지막 정차는 중간 정차로 세지 않는다.

각 승객에 대해 중간 정차 횟수의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 역의 개수 $N$, 열차 종류의 개수 $K$, 질의의 개수 $Q$가 공백으로 구분되어 주어진다. 다음 $N$개의 줄에는 각각 $i$번 역의 레벨 $L_i$가 한 정수로 주어진다. 다음 $Q$개의 줄에는 $k$번째 승객의 출발역 $A_k$와 목적지 $B_k$가 공백으로 구분되어 주어진다.

$Q$개의 줄을 출력한다. $k$번째 줄에는 역 $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$)