Farmer John acaba de colocar sus $N$ fardos de heno ($1 \leq N \leq 100,000$) en varios puntos del camino unidimensional que atraviesa su granja. Para asegurarse de que están separados adecuadamente, ayúdale a responder $Q$ consultas ($1 \leq Q \leq 100,000$), cada una de las cuales pregunta por el número de fardos en un intervalo específico del camino.

Entrada

La primera línea contiene $N$ y $Q$.

La siguiente línea contiene $N$ enteros distintos, cada uno en el intervalo $0 \ldots 1,000,000,000$, que indican que hay un fardo de heno en cada una de esas posiciones.

Cada una de las siguientes $Q$ líneas contiene dos enteros $A$ y $B$ ($0 \leq A \leq B \leq 1,000,000,000$), que dan una consulta sobre el número de fardos de heno entre $A$ y $B$, ambos incluidos.

Salida

Debes escribir $Q$ líneas de salida. Para cada consulta, imprime el número de fardos de heno en su intervalo correspondiente.

Ejemplos

Entrada 1

4 6
3 2 7 5
2 3
2 4
2 5
2 7
4 6
8 10

Salida 1

2
2
3
4
1
0

Autor del problema: Nick Wu