Se le proporciona un arreglo de ~n~ enteros y ~q~ consultas con la forma: ¿cuántos valores distintos hay en un rango ~[a,b]~?

Entrada

• La primera línea de entrada contiene dos enteros ~n~ y ~q~: el tamaño del arreglo y el número de consultas.
• La siguiente línea contiene ~n~ enteros ~x_1,x_2,\ldots,x_n~: los valores del arreglo.
• Finalmente, hay ~q~ líneas que describen las consultas. Cada línea contiene dos enteros ~a~ y ~b~.

Salida

Para cada consulta, imprima el número de valores distintos en el rango.

Restricciones

• ~1 \leq n,q \leq 2 \cdot 10^5~
• ~1 \leq x_i \leq 10^9~
• ~1 \leq a \leq b \le n~

Ejemplo de Entrada

5 3
3 2 3 1 2
1 3
2 4
1 5

Ejemplo de Salida

2
3
3