请注意,此问题中的内存限制比平常要少。
让我们考虑一个由正整数组成的数组,其中某些位置包含间隙。
我们有一系列可以用来填补空白的数字。给定集合中的每个数字最多可以使用一次。
你的任务是确定填充间隙的方式,使得所形成的数组中最长的递增子序列具有最大大小。
输入
第一行包含一个整数 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 只能用于替换两次。