Farmer John hat gerade seine $N$ Heuballen ($1 \leq N \leq 100,000$) an verschiedenen Punkten entlang der eindimensionalen Straße durch seine Farm aufgestellt. Um sicherzustellen, dass ihre Abstände angemessen sind, hilf ihm bei $Q$ Anfragen ($1 \leq Q \leq 100,000$), die jeweils nach der Anzahl der Heuballen in einem bestimmten Intervall der Straße fragen.

Eingabe

Die erste Zeile enthält $N$ und $Q$.

Die nächste Zeile enthält $N$ verschiedene ganze Zahlen, jeweils im Bereich $0 \ldots 1,000,000,000$. Sie geben an, dass sich an jeder dieser Positionen ein Heuballen befindet.

Jede der nächsten $Q$ Zeilen enthält zwei ganze Zahlen $A$ und $B$ ($0 \leq A \leq B \leq 1,000,000,000$), die eine Anfrage nach der Anzahl der Heuballen zwischen $A$ und $B$ einschließlich der Endpunkte angeben.

Ausgabe

Gib $Q$ Zeilen aus. Gib für jede Anfrage die Anzahl der Heuballen im zugehörigen Intervall aus.

Beispiele

Eingabe 1

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

Ausgabe 1

2
2
3
4
1
0

Aufgabenautor: Nick Wu