题目描述

Passport is a certificate which is used worldwide when a traveler enters foreign countries.

In a planet, there are $N$ countries, numbered from $1$ to $N$. Each country issues a passport. When a traveler has a passport issued by the country $i \ (1 \le i \le N)$, the traveler can enter the countries $L_i, L_{i + 1}, \dots, R_i$. Here, it is guaranteed that the traveler can enter the country where the passport was issued. Namely, $L_i \le i \le R_i$ is satisfied.

You have a friend who likes traveling. Although he dreams of traveling around the world, he does not have a passport in the beginning. Thus, he plans to visit all of the $N$ countries by repeating the following two actions.

• He gets a passport issued by the country where he is currently staying.
• He moves to a country where he can enter using a passport he currently has.

When you hear about his plan, you are wondering whether it is possible to realize the plan, and, if it is possible, what is the minimum number of passports he needs to get. Since you do not know where he lives, you consider $Q$ possible countries $X_1, X_2, \dots, X_Q$ where he lives.

Write a program which, given information of the passports and the possibilities of his living place, for each possibility, determines whether it is possible for him to visit all of the $N$ countries, and, if it is possible, calculates the minimum number of passports he needs to get.

输入格式

Read the following data from the standard input.

$N$

$L_1 \ R_1$

$L_2 \ R_2$

$\vdots$

$L_N \ R_N$

$Q$

$X_1$

$X_2$

$\vdots$

$X_Q$

输出格式

Write $Q$ lines to the standard output. The $j$-th line $(1 \le j \le Q)$ corresponds to the case where your friend lives in the country $X_j$. If it is possible for him to visit all of the $N$ countries, this line should contain the minimum number of passports he needs to get. Otherwise, this line should contain $-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

提示

【样例解释 #1】

Assume that your friend lives in the country $X_1 = 1$. It is possible for him to visit all of the $4$ countries if he acts in the following way. Then, he gets $2$ passports.

1. He gets a passport issued by the country $1$.
2. Using the passport issued by the country $1$, he moves to the country $2$.
3. He gets a passport issued by the country $2$.
4. Using the passport issued by the country $1$, he moves to the country $3$.
5. Using the passport issued by the country $2$, he moves to the country $44.

Since it is impossible to realize the plan if he gets less than or equal to $1$ passport, output $2$.

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

【样例解释 #2】

Assume that your friend lives in the country $X_1 = 3$. It is possible for him to visit all of the $5$ countries if he acts in the following way. Then, he gets $4$ passports.

1. He gets a passport issued by the country $3$.
2. Using the passport issued by the country $3$, he moves to the country $2$.
3. He gets a passport issued by the country $2$.
4. Using the passport issued by the country $2$, he moves to the country $4$.
5. He gets a passport issued by the country $4$.
6. Using the passport issued by the country $4$, he moves to the country $5$.
7. He gets a passport issued by the country $5$.
8. Using the passport issued by the country $5$, he moves to the country $1$.

Since it is impossible to realize the plan if he gets less than or equal to $3$ passports, output $4$.

该样例满足子任务 $2 \sim 5$ 的限制。

【样例解释 #3】

For example, if your friend lives in the country $X_3 = 3$, it is possible to realize the plan if he gets a passport issued by the country $3$, and uses it to visit the countries $1, 2, 4, 5$ in this order. Therefore, output $1$ in the third line.

On the other hand, if your friend lives in the country $X_5 = 5$, it is impossible for him to enter other countries even if he gets a passport issued by the country $5$. Thus, he cannot realize the plan. Therefore, output $-1$ in the fifth line.

该样例满足子任务 $4 \sim 5$ 的限制。

【样例解释 #4】

该样例满足子任务 $4 \sim 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_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$	无