分数: 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