Count in Range

Problem Description

An array $a$ of $n$ integers $a_1, a_2, \dots, a_n$ is given. It is necessary to answer queries of the form: «How many numbers in the array have values from $l$ to $r$ inclusive?».

Input Format

The first line contains an integer $n$ $(1 \le n \le 10^5)$ --- the length of the array.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ $$ --- the elements of the array.

The third line contains an integer $k$ $(1 \le k \le 10^5)$ --- the number of queries.

Then follow $k$ lines, each of which contains two integers $l$ and $r$ $(−10^9 \le l \le r \le 10^9)$ --- the bounds of the next query.

Output Format

For each query output one number --- the answer to it. Print all answers one per line.

5
7 1 8 10 5
6
2 100
4 7
1 9
1 10
2 4
9 9

4
2
4
5
0
0