第 3 题 Osumnjičeni (osumnjieni)

CSP-S 复赛模拟赛 25 · 时间限制 1.0 s · 空间限制 256 MB · 85 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 osumnjieni.in，输出文件 osumnjieni.out。

题目描述

现有 $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$ 行，表示每组询问的答案。

样例

样例 1

输入：

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

输出：

1
1
2

样例 2

输入：

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

输出：

1
1
1

样例 3

输入：

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

输出：

3
1
3

提示

【样例 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$。

【提示与说明】

**

**