题目描述

题目译自 JOISC 2023 Day1 T3 「パスポート / Passport」

护照是旅行者进入外国时在世界范围内使用的一种证件。

在一颗星球上有 $N$ 个国家，从 $1$ 到 $N$ 编号。每个国家签发一种护照。当旅行者持有国家 $i\ (1\le i\le N)$ 签发的护照时，他可以进入国家 $L_i,L_i+1,\ldots,R_i$。这里，保证旅行者可以进入所持护照的签发国。也就是说，保证 $L_i\le i\le R_i$。

你有一个喜欢旅行的朋友。他梦想环游世界，但他最开始没有护照。因此，他计划通过重复如下两个操作来环游所有的 $N$ 个国家。

• 他获得了他目前所在国家签发的护照
• 他移动到一个可以使用他目前拥有的护照入境的国家

当你听说了他的计划时，你想知道他是否可以实现他的计划，并且如果可以的话，他至少需要获得多少本护照。因为你不知道他住在哪儿，你假设他住在 $Q$ 个可能的国家 $X_1,X_2,\ldots,X_Q$。

给定护照和他可能居住的国家，写一个程序计算对于所有可能，他是否能够环游所有 $N$ 个国家，并且如果可能的话，计算他至少要获得多少本护照。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，每行两个整数 $L_i,R_i$。

接下来一行一个整数 $Q$。

接下来 $Q$ 行，每行一个整数 $X_j$。

输出格式

输出 $Q$ 行，对于第 $j$ 行输出你的朋友住在国家 $X_j$ 的情况的答案。如果他可以环游所有 $N$ 个国家，输出他最少获得护照本数。否则输出 $-1$。

4
1 3
2 4
2 3
4 4
1
1

2

假设你的朋友住在国家 $X_1=1$。如果他按照如下方法行动，他将环游所有 $4$ 个国家。然后他将获得 $2$ 本护照。

1. 他获得国家 $1$ 签发的护照。
2. 使用国家 $1$ 签发的护照，他移动到国家 $2$。
3. 他获得国家 $2$ 签发的护照。
4. 使用国家 $1$ 签发的护照，他移动到国家 $3$。
5. 使用国家 $2$ 签发的护照，他移动到国家 $4$。

因为如果他获得小于等于 $1$ 本护照的话无法实现计划，因此输出 $2$。

这组样例满足所有子任务的限制。

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

4

假设你的朋友住在国家 $X_1=3$。如果他按照如下方法行动，他将环游所有 $5$ 个国家。然后他将获得 $4$ 本护照。

1. 他获得国家 $3$ 签发的护照。
2. 使用国家 $3$ 签发的护照，他移动到国家 $2$。
3. 他获得国家 $2$ 签发的护照。
4. 使用国家 $2$ 签发的护照，他移动到国家 $4$。
5. 他获得国家 $4$ 签发的护照。
6. 使用国家 $4$ 签发的护照，他移动到国家 $5$。
7. 他获得国家 $5$ 签发的护照。
8. 使用国家 $5$ 签发的护照，他移动到国家 $1$。

因为如果他获得小于等于 $3$ 本护照的话无法实现计划，因此输出 $4$。

这组样例满足子任务 $2,3,4,5$ 的限制。

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

-1
2
1
2
-1

例如，如果你的朋友住在国家 $X_3=3$，如果他获得了国家 $3$ 签发的护照，他可以按 $1,2,4,5$ 的顺序前往这些国家来实现计划。因此，第三行输出 $1$。

另一方面，如果你的朋友住在国家 $X_5=5$，即使他获得了国家 $5$ 签发的护照，他也不可能进入其他国家。因此，他不能实现计划。因此第五行输出 $-1$。

这组样例满足子任务 $4,5$ 的限制。

4
1 2
1 2
3 4
3 4
4
1
2
3
4

-1
-1
-1
-1

这组样例满足子任务 $4,5$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $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_j\le N,X_j<X_{j+1}$

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
$1$	$Q=1,X_1=1$	$6$
$2$	$N\le 300,Q=1$	$16$
$3$	$N\le 2\ 500,Q=1$	$24$
$4$	$N\le 2\ 500$	$8$
$5$	无附加限制	$46$