Farmer John vient de disposer ses $N$ bottes de foin ($1 \leq N \leq 100,000$) en différents points de la route unidimensionnelle qui traverse sa ferme. Pour s’assurer qu’elles sont convenablement espacées, aidez-le à répondre à $Q$ requêtes ($1 \leq Q \leq 100,000$), chacune demandant le nombre de bottes de foin dans un intervalle précis de la route.

Entrée

La première ligne contient $N$ et $Q$.

La ligne suivante contient $N$ entiers distincts, chacun dans l’intervalle $0 \ldots 1,000,000,000$, indiquant qu’une botte de foin se trouve à chacune de ces positions.

Chacune des $Q$ lignes suivantes contient deux entiers $A$ et $B$ ($0 \leq A \leq B \leq 1,000,000,000$), donnant une requête sur le nombre de bottes de foin entre $A$ et $B$, bornes incluses.

Sortie

Vous devez afficher $Q$ lignes. Pour chaque requête, affichez le nombre de bottes de foin dans l’intervalle correspondant.

Exemples

Entrée 1

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

Sortie 1

2
2
3
4
1
0

Auteur du problème : Nick Wu