P9331 [JOIST 2023] 护照 / Passport

护照是旅行家进入他国时使用的证件。 在一个星球上有 $N$ 个国家，从 $1$ 到 $N$ 编号。每个国家都签发一种护照。当旅行家获得由国家$i \ (1 \le i \le N)$ 签发的护照后，他能够进入国家 $L_i, L_i + 1, \dots, R_i$。**这里保证旅行家能够进入其签证的签发国。形式上地说, $L_i \le i \le R_i$ 必然成立。** 你有一个爱旅行的朋友。即使他奢望能环游世界，但他最初一种护照也没有。因此，他想通过一下重复以下两项行为来环游这 $N$ 个国家。 - 获得他当前所在国家签发的护照。 - 用他现有的护照进入某个国家。 知道他的计划后，你想知道这个计划的是否可行，和如果可行的话，他最少需要的护照数量。因为你并不清楚他现在身处何国，所以你预测了 $Q$ 个他可能正居住在那的国家 $X_1, X_2, \dots, X_Q$。 现在给定各国护照的信息 $L_i, R_i$ 和他可能居住的 $Q$ 个国家，您需要写一个程序，对于每一个可能居住的国家，判断他是否可能环游这 $N$ 个国家，如果可能的话，计算出他需要的最少护照种数。

从标准输入读入： > $N$ > > $L_1 \ R_1$ > > $L_2 \ R_2$ > > $\vdots$ > > $L_N \ R_N$ > > $Q$ > > $X_1$ > > $X_2$ > > $\vdots$ > > $X_Q$

输出 $Q$ 行至标准输出，第 $j \ (1 \le j \le Q)$ 行一个整数代表若你的朋友位于国家 $X_j$ 的答案。若他能环游这 $N$ 个国家，则输出他需要的最少护照种数，否则输出 $-1$。

**【数据范围】** 对于所有测试数据，满足 $2 \le N \le 2 \times 10 ^ 5$，$1 \le L_i \le i \le R_i \le N$，$1 \le Q \le N$，$1 \le X_1 < X_2 < \dots < X_Q \le N$，保证所有输入均为整数。 |子任务编号|分值|限制| |:-:|:-:|:-:| |$1$|$6$|$Q = 1$，$X_1 = 1$| |$2$|$16$|$N \le 300$，$Q = 1$| |$3$|$24$|$N \le 2500$，$Q = 1$| |$4$|$8$|$N \le 2500$| |$5$|$46$|无| **【样例解释 #1】** 假设你的朋友居住在国家 $X_1 = 1$，一种可行的方式如下，最后他获得了 $2$ 种护照： 1. 获得国家 $1$ 签发的护照。 2. 用国家 $1$ 签发的护照去国家 $2$ 旅行。 3. 获得国家 $2$ 签发的护照。 4. 用国家 $1$ 签发的护照去国家 $3$ 旅行。 5. 用国家 $2$ 签发的护照去国家 $4$ 旅行。 可以证明不存在使用护照种数更小的方案，故输出 $2$。 该样例满足所有子任务的限制。 **【样例解释 #2】** 假设你的朋友居住在国家 $X_1 = 3$。一种可行的方式如下，最后他获得了 $4$ 种护照： 1. 获得国家 $3$ 签发的护照。 2. 用国家 $3$ 签发的护照去国家 $2$ 旅行。 3. 获得国家 $2$ 签发的护照。 4. 用国家 $2$ 签发的护照去国家 $4$ 旅行。 5. 获得国家 $4$ 签发的护照。 6. 用国家 $4$ 签发的护照去国家 $5$ 旅行。 7. 获得国家 $5$ 签发的护照。 8. 用国家 $5$ 签发的护照去国家 $1$ 旅行。 可以证明不存在使用护照种数更小的方案，故输出 $4$。 该样例满足子任务 $2 \sim 5$ 的限制。 **【样例解释 #3】** 例如，如果你的朋友居住在 $X_3 = 3$，一种可行的方案书获得国家 $3$ 签发的护照，并用它来依次去国家 $1, 2, 4, 5$ 旅行。故第三行输出 $3$。 但如果你的朋友居住在国家 $X_5 = 5$，即使他获得了国家 $5$ 签发的护照，他也不可能进入任何其他国家，因此，他无法实现自己的旅行计划。故第五行输出 $-1$。 该样例满足子任务 $4 \sim 5$ 的限制。 **【样例解释 #4】** 该样例满足子任务 $4 \sim 5$ 的限制。