5652: Fast search
[Creator : ]
Description
You are given an array $a$ of $n$ integers $a_1,\ a_2,\ \dots,\ a_n$.
Your task is to response to the queries like "How many numbers' values are between $l$ and $r$?".
Your task is to response to the queries like "How many numbers' values are between $l$ and $r$?".
Input
The first line of the input contains $n\ (1≤n≤10^5)$ — the length of the array.
The second line contains $n$ integers $a_1,\ a_2,\ \dots,\ a_n\ (-10^9≤a_i≤10^9)$.
The third line contains integer $k$ — the number of queries $(1≤k≤10^5)$.
The following $k$ lines contain a pair of integers $l\ r$ — query, described above $(-10^9≤l≤r≤10^9)$.
The second line contains $n$ integers $a_1,\ a_2,\ \dots,\ a_n\ (-10^9≤a_i≤10^9)$.
The third line contains integer $k$ — the number of queries $(1≤k≤10^5)$.
The following $k$ lines contain a pair of integers $l\ r$ — query, described above $(-10^9≤l≤r≤10^9)$.
Output
The output must consist of $k$ integers — responses for the queries.
Sample 1 Input
5
10 1 10 3 4
4
1 10
2 9
3 4
2 2
Sample 1 Output
5 2 2 0