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.
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.
You should write \(Q\) lines of output. For each query, output the number of haybales in its respective interval.
4 6 3 2 7 5 2 3 2 4 2 5 2 7 4 6 8 10
2 2 3 4 1 0