#4747. [Usaco2016 Dec]Counting Haybales

题目描述

Farmer John has just arranged his NN haybales (1≤N≤100,0001≤N≤100,000) at various points along t

he one-dimensional road running across his farm. To make sure they are spaced out appropriately, ple

ase help him answer QQ queries (1≤Q≤100,0001≤Q≤100,000), each asking for the number of haybales

within a specific interval along the road.

给出N（1≤N≤100,000）个数，和 Q（1≤Q≤100,000）个询问。每个询问包含两个整数A,B(0≤A≤B≤1,000,00

0,000）。对于每个询问，给出数值在A到B间的数有多少个（包含A与B）。

输入格式

The first line contains N and Q.The next line contains N distinct integers, each in the range 0…1,0

00,000,000 indicating that there is a haybale at each of those locations.Each of the next Q lines co

ntains two integers AA and BB (0≤A≤B≤1,000,000,000) giving a query for the number of haybales bet

ween A and B, inclusive.

输出格式

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

数据范围与提示