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