長さ $N$ の数列 $A_1, A_2, \ldots, A_N$ が与えられる。ここで、各要素は $1$ 以上 $K$ 以下の整数である。次のクエリを処理せよ:

• l r: 次の値を出力せよ: $\max\{|x - y| : l \le x, y \le r \text{ and } A_x = A_y\}$.

入力

最初の行には、数列の長さ $N$ と値の範囲 $K$ を表す 2 つの整数が与えられる。ただし $1 \le N \le 100{,}000$、$1 \le K \le 100{,}000$ である。

2 行目には、$N$ 個の整数 $A_1, A_2, \ldots, A_N$ が与えられる。ただし $1 \le A_i \le K$ である。

3 行目には、クエリの個数 $M$ を表す整数が与えられる。$1 \le M \le 100{,}000$ である。

続く $M$ 行のそれぞれには、クエリを表す 2 つの整数 $l, r$ が与えられる。ただし $1 \le l \le r \le N$ である。

出力

各クエリについて、答えを 1 行ずつ出力せよ。

入出力例

入力例 1

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

出力例 1

0
0
1
1
6