P7968 [COCI 2021/2022 #2] Osumnjičeni

现有 $n$ 个嫌疑人。由于其身高的不确定性，只知道每个嫌疑人的身高范围 $[l_i,r_i]$。 每次调查可以选取编号范围为 $[a,b]$ 内的所有嫌疑人，要求他们的身高范围没有交集。若嫌疑人在某次调查中出现，则目击者可以立即作出正确的判断。 给定 $q$ 组询问，每次给出 $p_i,q_i$。求在嫌疑人锁定在 $[p_i,q_i]$ 范围内的前提下，最多需要进行多少次调查。

第一行一个正整数 $n$，表示嫌疑人的数量。 接下来的 $n$ 行，每行两个正整数 $l_i,r_i$，表示第 $i$ 个嫌疑人的身高范围。 接下来的一行，一个正整数 $q$，表示询问组数。 接下来的 $q$ 行，每行两个正整数 $p_i,q_i$，表示一组询问。

共 $q$ 行，表示每组询问的答案。

**【样例 3 解释】** - 询问 $1,3$：在 $[1,1],[2,3],[4,5]$ 范围内进行调查即可，答案为 $3$。 - 询问 $2$：调查 $[3,5]$ 即可，答案为 $1$。 **【数据规模与约定】** **本题采用子任务捆绑测试。** - 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）：无特殊限制。 对于 $100\%$ 的数据，$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$。 **【提示与说明】** **题目译自 [COCI 2021-2022](https://hsin.hr/coci/) [CONTEST #2](https://hsin.hr/coci/contest2_tasks.pdf) _Task 5 Osumnjičeni_。** **本题分值按 COCI 原题设置，满分 $110$。**