Farmer John acabou de colocar seus $N$ fardos de feno ($1 \leq N \leq 100,000$) em vários pontos da estrada unidimensional que atravessa sua fazenda. Para garantir que estejam espaçados adequadamente, ajude-o a responder $Q$ consultas ($1 \leq Q \leq 100,000$), cada uma perguntando a quantidade de fardos de feno em um intervalo específico da estrada.

Entrada

A primeira linha contém $N$ e $Q$.

A próxima linha contém $N$ inteiros distintos, cada um no intervalo $0 \ldots 1,000,000,000$, indicando que há um fardo de feno em cada uma dessas posições.

Cada uma das próximas $Q$ linhas contém dois inteiros $A$ e $B$ ($0 \leq A \leq B \leq 1,000,000,000$), que descrevem uma consulta sobre a quantidade de fardos de feno entre $A$ e $B$, inclusive.

Saída

Você deve escrever $Q$ linhas de saída. Para cada consulta, imprima a quantidade de fardos de feno no intervalo correspondente.

Exemplos

Entrada 1

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

Saída 1

2
2
3
4
1
0

Créditos do problema: Nick Wu