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.
The first line contains n (1≤n≤105) and q (1≤q≤105). The next line contains n distinct integers, each in the range 0 ... 109, indicating that there is a haybale at each of those locations.
Each of the next q lines contains two integers a and b (0≤a≤b≤109) 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.