AT_tkppc6_2_m.山分け

编号为 $1$ 到 $N$ 的海盗，需要对编号为 $1$ 到 $10^{12}$ 的 $10^{12}$ 个宝藏进行分配。每个海盗都有自己对宝藏的偏好，具体来说，海盗 $i$ 只愿意接受编号在 $L_i$ 到 $R_i$ 范围内的宝藏。海盗之间有一个不成文的规则：编号大的海盗要接受编号小的海盗不想要的剩余宝藏。由于这个规则，所有 $i, j\ (1 \leq i < j \leq N)$ 均满足条件 $L_j \leq L_i$ 且 $R_i \leq R_j$。

海盗们一直在思考如何划分这些宝藏。现在，请你来解决以下 $Q$ 个查询：

• 在分配给海盗 $l, l+1, \ldots, r$ 时，每个海盗能分到的宝藏数量的最小值最大可能是多少？

输入是以如下格式从标准输入中给出的：

$N$ $L_1$ $R_1$ $L_2$ $R_2$ $\ldots$ $L_N$ $R_N$ $Q$ $\text{query}_1$ $\text{query}_2$ $\ldots$ $\text{query}_Q$

每个查询 $\text{query}_i$ 的结构为：

$l$ $r$

输出共 $Q$ 行，每行对应一个查询的答案，即第 $i\ (1 \leq i \leq Q)$ 行输出第 $i$ 个查询的结果。

• $2 \leq N \leq 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq L_i \leq R_i \leq 10^{12}$（$1 \leq i \leq N$）
• 满足所有 $i, j\ (1 \leq i < j \leq N)$：$L_j \leq L_i$ 且 $R_i \leq R_j$
• 每个查询满足 $1 \leq l \leq r \leq N$
• 所有输入数据均为整数

额外测试用例

如果程序能通过以下条件下的数据集（包括之前的 $800$ 分测试用例），可额外得到 $1$ 分。请注意，在这组数据集中使用低速语言可能会不通过：

• $2 \leq N \leq 5 \times 10^5$
• $1 \leq Q \leq 5 \times 10^5$

示例解释 1

对于第一个查询，例如可以这样分配宝藏：

• 将编号为 $2, 3$ 的宝藏给海盗 $1$，编号为 $4, 5$ 的宝藏给海盗 $2$。

对于第二个查询，可以让海盗 $2$ 获得编号为 $1, 2, 3, 4, 5$ 的所有宝藏。

原案：[penguinman](https://atcoder.jp/users/penguinman)

本翻译由 AI 自动生成