Haybale Counter

Farmer John has arranged N haybales along a one-dimensional road on his farm. He now wants to answer Q queries. Each query asks for the number of haybales located in an interval [L, R].

Formally, you are given a list of positions. For each query, count the number of haybales whose positions satisfy $$L \leq x \leq R$$.

inputFormat

The first line contains two integers $$N$$ and $$Q$$ (1 \leq N \leq 100,000 and 1 \leq Q \leq 100,000), representing the number of haybales and the number of queries respectively.

The second line contains $$N$$ space-separated integers, representing the positions of the haybales along the road.

Each of the next $$Q$$ lines contains two integers $$L$$ and $$R$$, describing a query for the interval [L, R].

outputFormat

For each query, output a single integer on a new line: the count of haybales found within the interval [L, R].

sample

5 3
3 8 1 5 10
2 8
4 4
1 10

3
0
5