Cho dãy $A_1, A_2, \ldots, A_N$ có độ dài $N$, trong đó mỗi số nằm trong khoảng từ $1$ đến $K$ (bao gồm cả hai đầu). Bạn cần xử lý các truy vấn sau:

• l r: in ra $\max\{|x - y| : l \le x, y \le r \text{ và } A_x = A_y\}$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $K$, thể hiện độ dài của dãy và khoảng giá trị. Ở đây $1 \le N \le 100{,}000$, $1 \le K \le 100{,}000$.

Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \ldots, A_N$, thỏa mãn $1 \le A_i \le K$.

Dòng thứ ba chứa một số nguyên $M$, thể hiện số lượng truy vấn, $1 \le M \le 100{,}000$.

$M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l, r$, thể hiện một truy vấn, thỏa mãn $1 \le l \le r \le N$.

Dữ liệu ra

Với mỗi truy vấn, in ra câu trả lời trên một dòng riêng biệt.

Ví dụ

Dữ liệu vào 1

7 7
4 5 6 6 5 7 4
5
6 6
5 6
3 5
3 7
1 7

Dữ liệu ra 1

0
0
1
1
6