题目描述

题目译自 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

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

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