| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 116 | 37 | 35 | 36.082% |
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ドル ≤ i ≤ 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 ≤ i ≤ 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.
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ドル ≤ j ≤ 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.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 6 | $Q = 1,ドル $X_1 = 1$. |
| 2 | 16 | $N ≤ 300,ドル $Q = 1$. |
| 3 | 24 | $N ≤ 2,500円,ドル $Q = 1$. |
| 4 | 8 | $N ≤ 2,500円$. |
| 5 | 46 | No additional constraints. |
4 1 3 2 4 2 3 4 4 1 1
2
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.
Since it is impossible to realize the plan if he gets less than or equal to 1ドル$ passport, output 2ドル$.
This sample input satisfies the constraints of all the subtasks.
5 1 5 2 4 2 3 3 5 1 5 1 3
4
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.
Since it is impossible to realize the plan if he gets less than or equal to 3ドル$ passports, output 4ドル$.
This sample input satisfies the constraints of Subtasks 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
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.
This sample input satisfies the constraints of Subtasks 4, 5.
4 1 2 1 2 3 4 3 4 4 1 2 3 4
-1 -1 -1 -1
This sample input satisfies the constraints of Subtasks 4, 5.