Problem Description

There are $n$ suspects. Due to uncertainty about their heights, we only know each suspect’s height range $[l_i, r_i]$.

In each investigation, you may choose all suspects whose indices are in a range $[a, b]$, and it is required that their height ranges do not intersect. If a suspect appears in an investigation, the witness can immediately make a correct identification.

You are given $q$ queries. Each query gives $p_i, q_i$. Under the condition that the suspects’ index range is $[p_i, q_i]$, find the minimum number of investigations needed.

Input Format

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

The next $n$ lines each contain two positive integers $l_i, r_i$, representing the height range of the $i$-th suspect.

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

The next $q$ lines each contain two positive integers $p_i, q_i$, representing one query.

Output Format

Output $q$ lines, where each line is the answer to the corresponding query.

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

Hint

[Sample 3 Explanation]

• Query $1,3$: It is enough to investigate within ranges $[1,1]$, $[2,3]$, and $[4,5]$, so the answer is $3$.
• Query $2$: Investigate $[3,5]$ only, so the answer is $1$.

[Constraints and Notes]

This problem uses bundled subtasks.

• Subtask 1 (10 pts): $q = p_1 = 1$, $q_1 = n$.
• Subtask 2 (10 pts): $1 \le n, q \le 5000$.
• Subtask 3 (20 pts): $1 \le n \le 5000$.
• Subtask 4 (20 pts): $1 \le q \le 100$.
• Subtask 5 (50 pts): No additional restrictions.

For $100\%$ of the testdata, $1 \le n, q \le 2 \times 10^5$, $1 \le a \le b \le n$, $1 \le l_i \le r_i \le 10^9$, $1 \le p_i \le q_i \le n$.

[Hints and Explanations]

Translated from COCI 2021-2022 CONTEST #2 Task 5 Osumnjičeni.

The score of this problem follows the original COCI settings, with a full score of $110$.

Translated by ChatGPT 5