You have just uploaded your first video as a content creator.

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 ~a~ and ~b~ inclusive ~(1 \le a, b \le 10^9)~ have watched your video?

Input Specification

The first line of input contains an integer ~N~.

The second line of input contains ~N~ space-separated integers ~x_i~.

The third line of input contains an integer ~Q~.

The next ~Q~ lines of input each contain ~2~ space-separated integers ~a~ and ~b~ ~(a \le b)~.

Output Specification

For each query, output the total number of viewers between the ages of ~a~ and ~b~ 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