수열과 쿼리 4

1 이상 $K$ 이하의 정수로 이루어진 길이 $N$의 수열 $A_1, A_2, \dots, A_N$이 주어진다. 다음 쿼리를 처리하는 프로그램을 작성하시오.

• l r: $\max\{|x - y| : l \le x,\, y \le r,\ A_x = A_y\}$를 출력한다.

$x$와 $y$가 같은 경우도 조건을 만족하므로 답은 항상 0 이상이다.

첫째 줄에 수열의 길이 $N$ ($1 \le N \le 100\,000$)과 $K$ ($1 \le K \le 100\,000$)가 주어진다.

둘째 줄에 $A_1, A_2, \dots, A_N$이 주어진다. ($1 \le A_i \le K$)

셋째 줄에 쿼리의 개수 $M$ ($1 \le M \le 100\,000$)이 주어진다.

넷째 줄부터 $M$개의 줄에 각 쿼리의 $l$과 $r$가 한 줄에 하나씩 주어진다. ($1 \le l \le r \le N$)

쿼리마다 답을 한 줄에 하나씩 입력에 주어진 순서대로 출력한다.