← 返回题目列表

Codeforces · 568/E

E. 最长递增子序列

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

请注意,此问题中的内存限制比平常要少。

让我们考虑一个由正整数组成的数组,其中某些位置包含间隙。

我们有一系列可以用来填补空白的数字。给定集合中的每个数字最多可以使用一次。

你的任务是确定填充间隙的方式,使得所形成的数组中最长的递增子序列具有最大大小。

输入

第一行包含一个整数 n — 数组的长度 (1 ≤ n ≤ 105)。

第二行包含 n 个空格分隔的整数 — 序列的元素。间隙标记为“-1”。不是间隙的元素是不超过109的正整数。保证序列包含0≤k≤1000个间隙。

第三行包含一个正整数 m — 填充间隙的元素数量 (k ≤ m ≤ 105)。

第四行包含 m 个正整数——用于填补空白的数字。每个数字都是不超过109的正整数。有些数字可能相等。

输出

在一行中打印 n 个空格分隔的数字 - 结果序列。如果有多个可能的答案,请打印其中任何一个。

示例

输入 #1

3
1 2 3
1
10

输出 #1

1 2 3

输入 #2

3
1 -1 3
3
1 2 3

输出 #2

1 2 3

输入 #3

2
-1 2
2
2 4

输出 #3

2 2

输入#4

3
-1 -1 -1
5
1 1 1 1 2

输出#4

1 1 2

输入 #5

4
-1 -1 -1 2
4
1 1 2 2

输出 #5

1 2 1 2

注意

第一个样本中没有间隙,因此正确答案是初始序列。

在第二个示例中,只有一种方法可以获得长度为 3 的递增子序列。

在第三个示例中,答案“4 2”也是正确的。请注意,仅考虑严格增加的子序列。

在第五个示例中,答案“1 1 1 2”被认为不正确,因为数字 1 只能用于替换两次。