## Counting Haybales

Points: 1
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
C, C++, Haskell, Java, Python

Farmer John has just arranged his $$N$$ haybales ($$1\leq N\leq 10^5$$) at various points along the one-dimensional road running across his farm. To make sure they are spaced out appropriately, please help him answer $$Q$$ queries ($$1\leq Q\leq 10^5$$), each asking for the number of haybales within a specific interval along the road.

Input

The first line contains $$N$$ and $$Q$$. The next line contains $$N$$ distinct integers, each in the range $$[0, 10^9]$$, indicating that there is a haybale at each of those locations. Each of the next $$Q$$ lines contains two integers $$A$$ and $$B$$ ($$0\leq A\leq B\leq 10^9$$) giving a query for the number of haybales between $$A$$ and $$B$$, inclusive.

Output

You should write $$Q$$ lines of output. For each query, output the number of haybales in its respective interval.

Sample Input

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

Sample Output

2
2
3
4
1
0

## Comments

There are no comments at the moment.