Công ty Đường sắt JOI vận hành một tuyến đường sắt thẳng gồm \(N\) ga, được đánh số từ \(1\) đến \(N\). Với mỗi \(1 \le i \le N-1\), ga \(i\) và ga \(i+1\) được nối bằng một đoạn đường ray.

Có \(K\) loại tàu chạy theo cả hai hướng, được đánh số từ \(1\) đến \(K\). Mỗi ga có một cấp độ từ \(1\) đến \(K\); ga \(i\) có cấp độ \(L_i\). Hai ga đầu mút, ga \(1\) và ga \(N\), đều có cấp độ \(K\).

Tàu loại \(j\) dừng tại mọi ga có cấp độ ít nhất \(j\) và không dừng tại các ga còn lại. Do hai ga đầu mút có cấp độ \(K\), mọi loại tàu đều dừng ở đó.

Trong hành trình, hành khách có thể đi tàu theo hướng ngược với đích, đi quá đích và đổi tàu tùy ý, nhưng cuối cùng phải dừng tại ga đích. Họ muốn tối thiểu hóa số lần dừng trung gian, không quan tâm đến số ga đi qua hay số lần đổi tàu. Nếu dừng ở một ga để đổi tàu, lần dừng đó được tính là một lần dừng trung gian. Lần dừng ban đầu tại ga xuất phát và lần dừng cuối tại ga đích không được tính.

Yêu cầu

Với mỗi truy vấn, tính số lần dừng trung gian ít nhất trên một hành trình từ ga xuất phát đến ga đích.

Dữ liệu vào

• Dòng đầu gồm ba số nguyên \(N,K,Q\): số ga, số loại tàu và số truy vấn.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(L_i\), là cấp độ của ga \(i\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(k\) gồm hai số nguyên \(A_k,B_k\), là ga xuất phát và ga đích của hành khách thứ \(k\).

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(k\) chứa số lần dừng trung gian ít nhất trên một hành trình từ ga \(A_k\) đến ga \(B_k\).

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(1 \le K \le N\).
• \(1 \le Q \le 100\,000\).
• \(1 \le L_i \le K\) với mọi \(1 \le i \le N\).
• \(1 \le A_k,B_k \le N\) với mọi \(1 \le k \le Q\).
• \(A_k \ne B_k\) với mọi \(1 \le k \le Q\).

Phân nhóm

1. Subtask 1 (5 điểm): \(N \le 100\), \(K \le 100\), \(Q \le 50\).
2. Subtask 2 (15 điểm): \(Q \le 50\).
3. Subtask 3 (25 điểm): \(K \le 20\).
4. Subtask 4 (55 điểm): Không có ràng buộc bổ sung.

Giới hạn

• Thời gian: 2 giây.
• Bộ nhớ: 512 MB.

Ví dụ

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

1
3
0

5 2 1
2
1
1
1
2
1 4

1

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

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