Age Demographic

View as PDF

Points: 7
Time limit: 3.0s
Memory limit: 512M

Author:
Problem type

Curious about which audiences you should be targeting, you have gathered data about $$N\:(1 \le N \le 3 \cdot 10^5)$$ different viewers. Specifically, you know the ages $$x_i\:(1 \le x_i \le 10^9)$$ of every single person that has watched your video.

Given $$Q\:(1 \le Q \le 3 \cdot 10^5)$$ different queries, how many people between the ages of and inclusive have watched your video?

Input Specification

The first line of input contains an integer .

The second line of input contains space-separated integers .

The third line of input contains an integer .

The next lines of input each contain space-separated integers and .

Output Specification

For each query, output the total number of viewers between the ages of and inclusive.

Sample Input

8
12 8 7 12 14 15 9 28
5
6 12
3 5
13 18
3 20
28 28

Sample Output

5
0
2
7
1