题目描述

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

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

提示

【样例 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 CONTEST #2 Task 5 Osumnjičeni。

本题分值按 COCI 原题设置，满分 $110$。