JOI Railways là một công ty vận hành một tuyến đường sắt. Trên tuyến đường sắt của JOI Railways có $N$ ga nằm trên một đường thẳng, được đánh số từ $1$ đến $N$. Với mỗi $i$ ($1\le i\le N-1$), ga $i$ và ga $i+1$ được nối với nhau bằng một đoạn đường ray.

JOI Railways có $K$ loại tàu chạy theo cả hai chiều. Các loại tàu được biểu diễn bằng những số nguyên từ $1$ đến $K$, kể cả hai đầu. Mỗi ga có một cấp độ là số nguyên từ $1$ đến $K$, kể cả hai đầu. Với mỗi $i$ ($1\le i\le N$), ga $i$ có cấp độ $L_i$. Hai ga ở hai đầu, tức ga $1$ và ga $N$, có cấp độ $K$.

Tàu loại $j$ ($1\le j\le K$) dừng ở mọi ga có cấp độ lớn hơn hoặc bằng $j$ và không dừng ở bất kỳ ga nào khác. Vì hai ga ở hai đầu, tức ga $1$ và ga $N$, có cấp độ $K$ nên mọi tàu đều dừng ở hai ga này.

Mỗi ngày có nhiều hành khách sử dụng JOI Railways. Trong hành trình, họ có thể đi tàu theo hướng ngược với ga đích, hoặc đi qua ga đích. Khi kết thúc hành trình, họ phải dừng ở ga đích. Họ không thích phải dừng ở các ga. Vì vậy, họ cố gắng chọn hành trình có số lần dừng trung gian ít nhất, bất kể số ga đi qua hay số lần đổi tàu. Nếu hành khách dừng ở một ga để đổi tàu thì ta tính đó là một lần dừng. Lần dừng đầu tiên ở ga xuất phát và lần dừng cuối cùng ở ga đích không được tính là những lần dừng trung gian.

Nhiệm vụ của bạn là viết chương trình trả lời các truy vấn về số lần dừng trung gian ít nhất cho từng hành khách.

Nhiệm vụ

Cho thông tin về tuyến đường sắt của JOI Railways cùng ga xuất phát và ga đích của từng hành khách, hãy viết chương trình trả lời các truy vấn về số lần dừng trung gian ít nhất cho từng hành khách.

Dữ liệu vào

Đọc dữ liệu sau từ đầu vào chuẩn.

• Dòng đầu tiên chứa ba số nguyên $N,K,Q$ cách nhau bởi dấu cách. Điều này có nghĩa JOI Railways có $N$ ga, có $K$ loại tàu và có $Q$ truy vấn về hành trình giữa hai ga.
• Dòng thứ $i$ ($1\le i\le N$) trong $N$ dòng tiếp theo chứa số nguyên $L_i$, cấp độ của ga $i$.
• Dòng thứ $k$ ($1\le k\le Q$) trong $Q$ dòng tiếp theo chứa hai số nguyên $A_i,B_i$ cách nhau bởi dấu cách. Điều này có nghĩa ga xuất phát và ga đích của hành khách thứ $k$ lần lượt là các ga $A_i,B_i$.

Dữ liệu ra

Ghi $Q$ dòng ra đầu ra chuẩn. Dòng thứ $k$ ($1\le k\le Q$) chứa số lần dừng trung gian ít nhất của một hành trình từ ga $A_k$ đến ga $B_k$.

Giới hạn

Tất cả dữ liệu vào thỏa mãn các điều kiện sau.

• $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$).

Nhiệm vụ con

Có 4 nhiệm vụ con. Điểm số và các giới hạn bổ sung của mỗi nhiệm vụ con như sau:

Nhiệm vụ con 1 [5 điểm]

• $N\le 100$.
• $K\le 100$.
• $Q\le 50$.

Nhiệm vụ con 2 [15 điểm]

• $Q\le 50$.

Nhiệm vụ con 3 [25 điểm]

• $K\le 20$.

Nhiệm vụ con 4 [55 điểm]

Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1
3
0

Ghi chú

Trong dữ liệu vào mẫu này, có ba truy vấn về hành trình giữa hai ga.

• Truy vấn thứ nhất hỏi về hành trình từ ga $2$ đến ga $4$. Nếu hành khách đi tàu loại $1$ từ ga $2$ đến ga $4$ thì chỉ có một lần dừng trung gian ở ga $3$.
• Truy vấn thứ hai hỏi về hành trình từ ga $4$ đến ga $9$. Nếu hành khách đi tàu loại $1$ từ ga $4$ đến ga $5$, sau đó đi tàu loại $2$ từ ga $5$ đến ga $1$, và cuối cùng đi tàu loại $3$ từ ga $1$ đến ga $9$ thì có ba lần dừng trung gian, ở các ga $5,1,8$.
• Truy vấn thứ ba hỏi về hành trình từ ga $6$ đến ga $7$. Nếu hành khách đi tàu loại $2$ từ ga $6$ đến ga $7$ thì không có lần dừng trung gian nào.

Dữ liệu vào 2

5 2 1
2
1
1
1
2
1 4

Dữ liệu ra 2

1

Ghi chú

Lưu ý rằng hành khách có thể đi qua ga đích trong hành trình.

Dữ liệu vào 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

Dữ liệu ra 3

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