Farmer John ha appena disposto le sue $N$ balle di fieno ($1 \leq N \leq 100,000$) in vari punti lungo la strada unidimensionale che attraversa la sua fattoria. Per assicurarsi che siano distanziate adeguatamente, aiutatelo a rispondere a $Q$ richieste ($1 \leq Q \leq 100,000$), ognuna delle quali chiede il numero di balle di fieno in uno specifico intervallo della strada.

Input

La prima riga contiene $N$ e $Q$.

La riga successiva contiene $N$ interi distinti, ciascuno nell’intervallo $0 \ldots 1,000,000,000$, che indicano la presenza di una balla di fieno in ognuna di quelle posizioni.

Ognuna delle successive $Q$ righe contiene due interi $A$ e $B$ ($0 \leq A \leq B \leq 1,000,000,000$), che descrivono una richiesta sul numero di balle di fieno tra $A$ e $B$, estremi inclusi.

Output

Scrivete $Q$ righe di output. Per ogni richiesta, stampate il numero di balle di fieno nel rispettivo intervallo.

Esempi

Input 1

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

Output 1

2
2
3
4
1
0

Autore del problema: Nick Wu