Suspects

Time limit1sMemory limit512 MB

Summary

Each suspect has a height interval; a lineup is a contiguous range whose intervals admit distinct reals. For each query range [p,q], report the minimum number of such lineups needed in the worst case.

Level: Hard8 of 10
Topics: Intervals, Greedy, Dynamic programming, Sorting
Solved: No attempts yet

Problem

In a police investigation, n suspects were identified, and now the witnesses must try to find the perpetrator. The height of every suspect i was measured, but because the measurement is unreliable, all that is known is that the height is a real number in the interval $[l_i, r_i]$ . At most one suspect is the perpetrator, and it is possible that none of them is.

A single lineup consists of choosing two positive integers a and b ( $1 \le a \le b \le n$ ), then taking suspects a, a+1, ..., b to a separate room so that the witnesses can try to identify the perpetrator. Because the witnesses could be confused if two 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 now wants to answer 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 can find the perpetrator or report that he is not among the suspects?" Help the lead investigator answer q 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

Print the answers to the corresponding questions in q lines: the minimum required number of lineups.

Constraints

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

Hint

Clarification of the third example:

For the first and the third question, three lineups are sufficient: one consists of suspect 1, one consists of suspects 2 and 3, and one consists of suspects 4 and 5.

For the second question, one lineup consisting of suspects 3, 4 and 5 is sufficient.

Examples3

Example 1
Input
```
2
1 1
1 1
3
1 1
2 2
1 2
```
Expected output
```
1
1
2
```
Example 2
Input
```
3
1 1
2 2
3 3
3
1 1
2 3
1 3
```
Expected output
```
1
1
1
```

Example 3

Input

Expected output

3
1
3