El conejo saltarín se encuentra tranquilamente saltando en una hilera de ~n~ piedras, numeradas de ~1~ a ~n~, donde ~a_i~ es la posición de la ~i~-ésima piedra.

Se garantiza que ~a_i > a_{i-1}~ para todo ~2 \leq i \leq n~, es decir, la posición de una piedra es mayor que la de la piedra anterior.

El conejo tiene un límite de salto ~k~, por lo que puede realizar un salto de la piedra ~x~ a la piedra ~y~ si y solo si ~| a_x - a_y | \leq k~.

El conejo tiene ~q~ consultas de la forma ~x, y~, quiere saber cuál es la mínima cantidad de saltos que debe realizar para ir de la piedra ~x~ a la piedra ~y~, o si es imposible hacer esto, saltando solamente entre piedras.

Entrada:

La primera línea contendrá dos enteros ~n~ y ~k~ ~(2 \leq n \leq 200\,000)~, ~(1 \leq k \leq 200\,000)~, la cantidad de piedras y el límite de salto del conejo respectivamente.

La segunda línea contendrá ~n~ enteros ~a_1, a_2, \cdots, a_n~ ~(1 \leq a_i \leq 200\,000)~, donde ~a_i~ es la posición de la ~i~-ésima piedra, se garantiza que ~a_i > a_{i-1}~ para todo ~2 \leq i \leq n~.

La tercera línea contendrá un entero ~q~ ~(1 \leq q \leq 200\,000)~, la cantidad de consultas a procesar.

Cada una de las siguientes ~q~ líneas contendrá dos enteros ~x~ y ~y~ ~(1 \leq x \leq y \leq n)~, las dos piedras de dicha consulta.

Salida

Imprima ~q~ líneas con un entero cada una, el resultado de cada consulta, la mínima cantidad de saltos que debe realizar el conejo para ir de la piedra ~x~ a la piedra ~y~, o ~-1~ si es imposible ir de ~x~ a ~y~.

Subtareas:

• Subtarea 1: ~a = 1, 2, \cdots, n~, es decir, ~a~ es una permutación ascendente (10 puntos)
• Subtarea 2: Se garantiza que existe un entero positivo ~const~, tal que ~a_i - a_{i-1} = const~ para todo ~2 \leq i \leq n~ (10 puntos)
• Subtarea 3: Se garantiza que ~n \cdot q \leq 1\,000\,000~ (28 puntos)
• Subtarea 4: ~k \geq 10\,000, q \leq 10\,000~ (27 puntos)
• Subtarea 5: Sin restricciones adicionales (25 puntos)

Ejemplo de entrada:

7 4
1 5 8 9 10 12 17
5
1 6
2 6
3 5
4 6
1 7

Ejemplo de salida:

3
2
1
1
-1