Problem D
Massive Card Game

You and a friend have been playing a card game for a while. In the game, a player has a list of cards, each containing an integer. The goal is to guess exactly what cards the opponent has. To accomplish this, they take turns asking the opponent how many of the integers on their cards are in a given range.

Normally, answering this question is simple – just count the cards. To make the game a bit harder, your friend proposed instead playing a massive variant of the game, where each player can have up to $100\, 000$ cards! Answering the opponent’s questions by counting cards one at a time is now quite slow... Perhaps you could write a computer program to answer these questions a bit faster?

Input

The first line of the input contains an integer $N$ ($1 \le N \le 100\, 000$), the number of cards one of the players has. The next line contains the $N$ integers written on the player’s cards, each between $0$ and $10^9$.

The next line contains an integer $Q$ ($1 \le Q \le 100\, 000$), the number of ranges to count cards in. The next $Q$ lines each contains two integers $l$ and $r$ ($0 \le l \le r \le 10^9$), the integer range given in a question.

Output

For each range $[l, r]$, output the number of cards with an integer $x$ such that $l \le x \le r$.

5
1 2 3 4 5
5
1 5
3 4
2 2
6 6
0 0

5
2
1
0
0

10
4 2 4 2 4 2 4 2 4 2
2
2 2
4 4

5
5