← 返回题目列表

AtCoder · agc013_f

F. 两张牌

中文机器翻译题面 查看原题

分数: 2000 点

问题陈述

有 N 卡。每张卡片的两面都是可区分的。 的 i- 第一张卡片有一个整数 A_i 印在正面,另一个整数 背面印有 B_i 。 我们将把这些牌称为牌组 X。 还有 N+1 另一种卡片。 的 正面印有 i- 第一张卡片有一个整数 C_i ,背面未印任何内容。 我们将其称为另一副牌 Y.

你会玩 Q 游戏回合。 每一轮都是独立进行的。 在 i- 第轮,您将获得一张新卡。这张卡的两面是可区分的。 它有一个整数 D_i 印在正面,另一个整数 背面印有 E_i 印在背面。 一副新的牌 Z 是通过将此卡添加到 X。 然后,您会被要求形成 N+1 成对的卡片,每张由一张卡片组成 Z 和一张来自 Y。 每张牌必须恰好属于其中一对。 此外,对于每张卡 Z,需要指定哪一侧 使用。 对于每一对,必须满足以下条件:

  • (打印在卡片已用面的整数 Z) \leq (卡上打印的整数 Y)

如果无论如何组队以及使用哪边都无法满足此条件,则该轮的得分将 -1。 否则,该回合的得分将是以下牌的数量 使用正面的 Z 。

找出每轮的最大可能得分。

约束

  • 所有输入值均为整数。
  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq A_i ,B_i ,C_i ,D_i ,E_i \leq 10^9

输入

输入由标准输入按以下格式给出:

N
A_1 B_1
A_2 B_2
:
A_N B_N
C_1 C_2 .. C_{N+1}
Q
D_1 E_1
D_2 E_2
:
D_Q E_Q

输出

对于每一轮,在其自己的行中打印可能的最大分数。


样本输入 1

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

示例输出 1

0
1
2

例如,在第三轮中,牌 Z 是 (4,1),(5,3),(3,1),(2,3)。 得分为 2 可以通过使用它们的正面,背面,背面和正面,并将它们与第四,第三,第一和第二张牌配对来获得 分别是 Y。 不可能获得分数 3 或更大,因此答案是 2.


示例输入 2

5
7 1
9 7
13 13
11 8
12 9
16 7 8 6 9 11
7
6 11
7 10
9 3
12 9
18 16
8 9
10 15

示例输出 2

4
3
3
1
-1
3
2

示例输入 3

9
89 67
37 14
6 1
42 25
61 22
23 1
63 60
93 62
14 2
67 96 26 17 1 62 56 92 13 38
11
93 97
17 93
61 57
88 62
98 29
49 1
5 1
1 77
34 1
63 27
22 66

示例输出 3

7
9
8
7
7
9
9
10
9
7
9