7908: USACO 2016 December Contest, Silver —— Problem 1. Counting Haybales
[Creator : ]
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.
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.
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.
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