CF568E Longest Increasing Subsequence

注意，本题的内存限制比平常更低。 给定一个只包含正整数的数组，其中有些位置是空缺。 你有一个备选数集，可以用来填补空缺。每个备选数最多只能使用一次。 你的任务是确定如何填补这些空缺，以使形成的新数组中的最长严格递增子序列的长度最大。

第一行包含一个整数 $n$，表示数组的长度（$1 \leq n \leq 10^{5}$）。 第二行包含 $n$ 个用空格分隔的整数，表示该数组。用 $-1$ 表示空缺。非空缺处为不超过 $10^9$ 的正整数。保证序列中空缺的个数 $0 \leq k \leq 1000$。 第三行包含一个正整数 $m$，表示可用的备选数的个数（$k \leq m \leq 10^5$）。 第四行包含 $m$ 个正整数，表示可用的填补数字。每个数字不超过 $10^9$，其中一些数字可能相同。

输出 $n$ 个用空格分隔的整数，表示填补空缺后得到的新序列。如果有多组解，输出任意一组均可。

在第一个样例中，没有空缺，因此答案就是原始数组。 在第二个样例中，只有一种方式可以得到长度为 $3$ 的严格递增子序列。 在第三个样例中，答案“4 2”同样正确。注意只计算严格递增子序列。 在第五个样例中，答案“1 1 1 2”不正确，因为数字 $1$ 最多只能用两次。 由 ChatGPT 5 翻译