Problems
Counting Haybales
Counting Haybales
Farmer John has just arranged his $n$ haybales 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, each asking for the number of haybales within a specific interval along the road.
\InputFile
The first line contains $n~(1 \le n \le 10^5)$ and $q~(1 \le q \le 10^5)$. 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 \le a \le b \le 10^9)$ giving a query for the number of haybales between $a$ and $b$, inclusive.
\OutputFile
You should write $q$ lines of output. For each query, output the number of haybales in its respective interval.
Input example #1
4 6 3 2 7 5 2 3 2 4 2 5 2 7 4 6 8 10
Output example #1
2 2 3 4 1 0