题目描述

样例

有 $n$ 个宝箱，编号为 $1,2,\ldots,n$，初始都上锁。宝箱 $i$ 中有一枚编号为 $i$ 的金币。获得某个宝箱的钥匙后，就可以免费打开它并取出其中的金币。

你可以支付已经获得的金币 $i$，一次购买宝箱 $L_i,L_i+1,\ldots,R_i$ 的全部钥匙，其中 $1\le L_i\le i\le R_i\le n$。支付会消耗这枚金币；同一个宝箱中的金币只能获得一次。已经获得的钥匙以及已经打开的宝箱不会因支付而失去。

有 $q$ 个互相独立的询问。每个询问给定一个编号 $s$：假设初始只拥有宝箱 $s$ 的钥匙，没有任何金币，最少需要支付多少枚金币，才能打开全部 $n$ 个宝箱？无法做到时输出 $-1$。

每次支付计为一枚金币，金币的编号不是它的价值。

输入格式

从标准输入读入。

第一行包含整数 $n$。

接下来 $n$ 行，第 $i$ 行包含两个整数 $L_i,R_i$。

接下来一行包含整数 $q$。

接下来 $q$ 行，每行包含整数 $s$，表示一个询问。

输出格式

向标准输出写出 $q$ 行，依次回答各个询问。每行输出最少支付的金币枚数；无法打开全部宝箱时输出 $-1$。

数据范围

所有输入均为整数，满足：

• $1\le n\le 2\times10^5$；
• $1\le L_i\le i\le R_i\le n$；
• $1\le q\le n$；
• 每次询问满足 $1\le s\le n$。

子任务

样例 1

4
1 3
2 4
2 3
4 4
1
1

2

样例 1 说明

先打开宝箱 $1$，支付金币 $1$ 获得宝箱 $1,2,3$ 的钥匙；打开宝箱 $2$ 后支付金币 $2$，即可再获得宝箱 $4$ 的钥匙。共支付 $2$ 枚金币。只支付金币 $1$ 还不能打开宝箱 $4$。

样例 2

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

4

样例 2 说明

初始打开宝箱 $3$。可以依次支付金币 $3,2,4,5$：可打开的宝箱范围依次变为 $[2,3]$、$[2,4]$、$[2,5]$、$[1,5]$。前两次支付只能依次选择能扩展范围的金币 $3,2$；随后还必须先打开宝箱 $5$ 才能获得宝箱 $1$ 的钥匙，因此需要 $4$ 枚金币。

样例 3

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

-1
2
1
2
-1

样例 3 说明

从宝箱 $3$ 出发，支付金币 $3$ 即可打开所有宝箱。从宝箱 $2$ 或 $4$ 出发，可以先取得宝箱 $3$ 中的金币，再支付它，共用 $2$ 枚金币。宝箱 $1$ 和 $5$ 中的金币分别只能换到本箱的钥匙，从它们出发都无法继续扩展。