Counting Haybales
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
Farmer John has just arranged his N haybales ( 1≤N≤100,000) 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≤Q≤100,000), 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…1,000,000,000, 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≤1,000,000,000) 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.
样例 1
样例输入
4 6
3 2 7 5
2 3
2 4
2 5
2 7
4 6
8 10
样例输出
2
2
3
4
1
0
限制
各个测试点1s,256MB内存空间。