题目描述

护照是旅行家进入他国时使用的证件。

在一个星球上有 $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$。

题目大意

题目描述

护照是旅行家进入他国时使用的证件。

在一个星球上有 $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$。

提示

【样例解释 #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$ 的限制。

4
1 3
2 4
2 3
4 4
1
1

2

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

4

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

-1
2
1
2
-1

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

-1
-1
-1
-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$ 的限制。