Description

Problem from COCI 2021/2022 Contest #2 T5「Suspects」

In a police investigation, $n$ suspects were identified and now it's up to the witnesses to try to find the perpetrator. The height of every suspect $i$ was measured, but due to the unreliability of measurement, it is known only that their height is a real number from the interval from $l_i$ to $r_i$ (inclusive). At most one of the suspects is the perpetrator, and it could be the case that none of them are.

A single lineup consists of choosing two positive integers $a$ and $b$ $(1 \le a \le b \le n)$, then taking the suspects $a, a + 1, \ldots, b$ to a separate room so that the witnesses could try to identify the perpetrator. As the witnesses could be confused if two of the suspects have the same height, a lineup is allowed only if it is possible to guarantee that no two suspects will have the same height. During a lineup, the witnesses will always be able to identify the perpetrator if he is among the chosen suspects, or they will be able to tell that he is not among them.

The lead investigator is now interested in answering questions of the following form: "If I were certain that the label of the perpetrator could only be between $p$ and $q$ $(p \le q)$, what is the minimum number of lineups needed in the worst case so that the witnesses are able to find the perpetrator, or report that he is not among the suspects?" Help the lead investigator answer $q$ of such questions.

Input

The first line contains a positive integer $n$, the number of suspects.

The following $n$ lines contain two positive integers $l_i$ and $r_i$ $(1 \le l_i \le r_i \le 10^9)$ which represent the possible height range of the suspect with label $i$.

The next line contains a positive integer $q$, the number of questions.

The following $q$ lines contain two positive integers $p_i$ and $q_i$ $(1 \le p_i \le q_i \le n)$ which determine a question.

Output

In $q$ lines print the answers to the corresponding questions: the minimum required number of lineups.

2
1 1
1 1
3
1 1
2 2
1 2

1
1
2

3
1 1
2 2
3 3
3
1 1
2 3
1 3

1
1
1

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

3
1
3

Scoring

In every subtask, it holds that $1 \le n, q \le 200\ 000$.