Problem7908--USACO 2016 December Contest, Silver —— Problem 1. Counting Haybales

7908: USACO 2016 December Contest, Silver —— Problem 1. Counting Haybales

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

Farmer John has just arranged his $N\ (1≤N≤100,000)$ 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\ (1≤Q≤100,000)$ queries, 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 \sim 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, B\ (0≤A≤B≤1,000,000,000)$ 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 1 Input

4 6
3 2 7 5
2 3
2 4
2 5
2 7
4 6
8 10

Sample 1 Output

2
2
3
4
1
0

HINT

相同题目:USACO Silver

Source/Category