JOI 철도는 하나의 철도 노선을 운영하는 회사입니다. JOI 철도의 노선에는 일직선 위에 $1$부터 $N$까지 번호가 매겨진 $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$이므로 모든 열차는 이 두 역에 정차합니다.

매일 많은 승객들이 JOI 철도를 이용합니다. 여행 도중 승객들은 목적지와 반대 방향으로 가는 열차를 탈 수도 있고, 목적지를 지나쳐 갈 수도 있습니다. 여행의 마지막에는 반드시 목적지에 정차해야 합니다. 승객들은 역에 정차하는 것을 별로 좋아하지 않습니다. 따라서 통과한 역의 수나 환승 횟수에 관계없이 중간 정차 횟수가 최소인 경로를 이용하려고 합니다. 승객이 열차를 갈아타기 위해 역에 정차하면 이는 한 번의 정차로 계산합니다. 출발역에서의 첫 정차와 목적지에서의 마지막 정차는 중간 정차로 간주하지 않습니다.

각 승객에 대해 최소 중간 정차 횟수에 관한 쿼리에 답하는 프로그램을 작성하는 것이 당신의 과제입니다.

과제

JOI 철도의 노선 정보와 각 승객의 출발역 및 목적지가 주어졌을 때, 각 승객에 대해 최소 중간 정차 횟수에 관한 쿼리에 답하는 프로그램을 작성하십시오.

입력 형식

표준 입력에서 다음 데이터를 읽으십시오.

• 입력의 첫 번째 줄에는 공백으로 구분된 세 정수 $N,K,Q$가 주어집니다. 이는 JOI 철도에 $N$개의 역이 있고, $K$종류의 열차가 있으며, 두 역 사이의 여행에 관한 $Q$개의 쿼리가 주어짐을 의미합니다.
• 이어지는 $N$개의 줄 중 $i$번째 줄($1\le i\le N$)에는 역 $i$의 등급을 나타내는 정수 $L_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$에서 역 $4$까지 종류 $1$인 열차를 타면 중간 정차는 역 $3$에서 단 한 번만 발생합니다.
• 두 번째 쿼리는 역 $4$에서 역 $9$로의 여행에 관한 것입니다. 승객이 역 $4$에서 역 $5$까지 종류 $1$인 열차를 타고, 역 $5$에서 역 $1$까지 종류 $2$인 열차를 탄 다음, 마지막으로 역 $1$에서 역 $9$까지 종류 $3$인 열차를 타면 중간 정차는 역 $5,1,8$의 세 번 발생합니다.
• 세 번째 쿼리는 역 $6$에서 역 $7$로의 여행에 관한 것입니다. 승객이 역 $6$에서 역 $7$까지 종류 $2$인 열차를 타면 중간 정차가 없습니다.

입력 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