Dany jest ciąg $A_1, A_2, \ldots, A_N$ długości $N$, w którym każda liczba znajduje się w przedziale od $1$ do $K$ włącznie. Należy obsłużyć następujące zapytania:

• l r: wypisz $\max\{|x - y| : l \le x, y \le r \text{ oraz } A_x = A_y\}$.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $N$ i $K$, oznaczające długość ciągu oraz zakres wartości. Tutaj $1 \le N \le 100\,000$, $1 \le K \le 100\,000$.

Drugi wiersz zawiera $N$ liczb całkowitych $A_1, A_2, \ldots, A_N$, spełniających $1 \le A_i \le K$.

Trzeci wiersz zawiera liczbę całkowitą $M$, oznaczającą liczbę zapytań, $1 \le M \le 100\,000$.

Kolejne $M$ wierszy zawiera po dwie liczby całkowite $l, r$, reprezentujące zapytanie, spełniających $1 \le l \le r \le N$.

Wyjście

Dla każdego zapytania wypisz odpowiedź w osobnym wierszu.

Przykład

Wejście 1

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

Wyjście 1

0
0
1
1
6