Wheel Battle Garden Query

The king has a garden with \(n\) trees, each tree is positioned on a number line at an integer coordinate. The king's \(m\) knights will, one by one, challenge you with a query: given a range \([L, R]\), determine how many trees are located within this range (inclusive). If you fail to answer any query immediately, your service is done!

Formally, you are given \(n\) integers representing the coordinates of the trees. Then, you are given \(m\) queries. Each query consists of two integers \(L\) and \(R\); for each query, output the number of trees whose coordinates \(x\) satisfy \(L \le x \le R\).

inputFormat

The first line contains two integers \(n\) and \(m\) - the number of trees and the number of queries, respectively.

The second line contains \(n\) space-separated integers representing the coordinates of the trees.

Then \(m\) lines follow. Each of these lines contains two space-separated integers \(L\) and \(R\) representing a query.

outputFormat

For each query, output a single integer on a new line - the number of trees that have coordinates in the range \([L, R]\) (inclusive).

sample

5 3
1 3 5 7 9
1 5
4 8
10 15

3
2
0