P7968 [COCI 2021/2022 #2] Suspects

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.

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 $q$ lines, where each line is the answer to the corresponding query.

**[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](https://hsin.hr/coci/) [CONTEST #2](https://hsin.hr/coci/contest2_tasks.pdf) _Task 5 Osumnjičeni_.** **The score of this problem follows the original COCI settings, with a full score of $110$.** Translated by ChatGPT 5