{"raw_statement":[{"iden":"statement","content":"护照是旅行家进入他国时使用的证件。\n\n在一个星球上有 $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\n你有一个爱旅行的朋友。即使他奢望能环游世界，但他最初一种护照也没有。因此，他想通过一下重复以下两项行为来环游这 $N$ 个国家。\n\n- 获得他当前所在国家签发的护照。\n- 用他现有的护照进入某个国家。\n\n知道他的计划后，你想知道这个计划的是否可行，和如果可行的话，他最少需要的护照数量。因为你并不清楚他现在身处何国，所以你预测了 $Q$ 个他可能正居住在那的国家 $X_1, X_2, \\dots, X_Q$。\n\n现在给定各国护照的信息 $L_i, R_i$ 和他可能居住的 $Q$ 个国家，您需要写一个程序，对于每一个可能居住的国家，判断他是否可能环游这 $N$ 个国家，如果可能的话，计算出他需要的最少护照种数。"},{"iden":"input","content":"从标准输入读入：\n\n> $N$\n>\n> $L_1 \\ R_1$\n>\n> $L_2 \\ R_2$\n>\n> $\\vdots$\n>\n> $L_N \\ R_N$\n>\n> $Q$\n>\n> $X_1$\n>\n> $X_2$\n>\n> $\\vdots$\n>\n> $X_Q$"},{"iden":"output","content":"输出 $Q$ 行至标准输出，第 $j \\ (1 \\le j \\le Q)$ 行一个整数代表若你的朋友位于国家 $X_j$ 的答案。若他能环游这 $N$ 个国家，则输出他需要的最少护照种数，否则输出 $-1$。"},{"iden":"note","content":"**【数据范围】**\n\n对于所有测试数据，满足 $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$，保证所有输入均为整数。\n\n|子任务编号|分值|限制|\n|:-:|:-:|:-:|\n|$1$|$6$|$Q = 1$，$X_1 = 1$|\n|$2$|$16$|$N \\le 300$，$Q = 1$|\n|$3$|$24$|$N \\le 2500$，$Q = 1$|\n|$4$|$8$|$N \\le 2500$|\n|$5$|$46$|无|\n\n**【样例解释 #1】**\n\n假设你的朋友居住在国家 $X_1 = 1$，一种可行的方式如下，最后他获得了 $2$ 种护照：\n\n1. 获得国家 $1$ 签发的护照。\n2. 用国家 $1$ 签发的护照去国家 $2$ 旅行。\n3. 获得国家 $2$ 签发的护照。\n4. 用国家 $1$ 签发的护照去国家 $3$ 旅行。\n5. 用国家 $2$ 签发的护照去国家 $4$ 旅行。\n\n可以证明不存在使用护照种数更小的方案，故输出 $2$。\n\n该样例满足所有子任务的限制。\n\n**【样例解释 #2】**\n\n假设你的朋友居住在国家 $X_1 = 3$。一种可行的方式如下，最后他获得了 $4$ 种护照：\n\n1. 获得国家 $3$ 签发的护照。\n2. 用国家 $3$ 签发的护照去国家 $2$ 旅行。\n3. 获得国家 $2$ 签发的护照。\n4. 用国家 $2$ 签发的护照去国家 $4$ 旅行。\n5. 获得国家 $4$ 签发的护照。\n6. 用国家 $4$ 签发的护照去国家 $5$ 旅行。\n7. 获得国家 $5$ 签发的护照。\n8. 用国家 $5$ 签发的护照去国家 $1$ 旅行。\n\n可以证明不存在使用护照种数更小的方案，故输出 $4$。\n\n该样例满足子任务 $2 \\sim 5$ 的限制。\n\n**【样例解释 #3】**\n\n例如，如果你的朋友居住在 $X_3 = 3$，一种可行的方案书获得国家 $3$ 签发的护照，并用它来依次去国家 $1, 2, 4, 5$ 旅行。故第三行输出 $3$。\n\n但如果你的朋友居住在国家 $X_5 = 5$，即使他获得了国家 $5$ 签发的护照，他也不可能进入任何其他国家，因此，他无法实现自己的旅行计划。故第五行输出 $-1$。\n\n该样例满足子任务 $4 \\sim 5$ 的限制。\n\n**【样例解释 #4】**\n\n该样例满足子任务 $4 \\sim 5$ 的限制。"}],"translated_statement":null,"sample_group":[["4\n1 3\n2 4\n2 3\n4 4\n1\n1\n","2\n"],["5\n1 5\n2 4\n2 3\n3 5\n1 5\n1\n3\n","4\n"],["5\n1 1\n2 3\n1 5\n3 4\n5 5\n5\n1\n2\n3\n4\n5\n","-1\n2\n1\n2\n-1\n"],["4\n1 2\n1 2\n3 4\n3 4\n4\n1\n2\n3\n4\n","-1\n-1\n-1\n-1\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}