CF568E.Longest Increasing Subsequence

Note that the memory limit in this problem is less than usual.

Let's consider an array consisting of positive integers, some positions of which contain gaps.

We have a collection of numbers that can be used to fill the gaps. Each number from the given collection can be used at most once.

Your task is to determine such way of filling gaps that the longest increasing subsequence in the formed array has a maximum size.

注意：本题的内存限制小于常规限制。

考虑一个由正整数组成的数组，其中某些位置为空（即存在空缺）。

我们拥有一组可用于填补空缺的数字。给定集合中的每个数字至多只能使用一次。

你的任务是确定一种填补空缺的方式，使得所形成的数组的最长递增子序列（LIS）的长度达到最大。

The first line contains a single integer n — the length of the array (1 ≤ n ≤ 105).

The second line contains n space-separated integers — the elements of the sequence. A gap is marked as "-1". The elements that are not gaps are positive integers not exceeding 109. It is guaranteed that the sequence contains 0 ≤ k ≤ 1000 gaps.

The third line contains a single positive integer m — the number of elements to fill the gaps (k ≤ m ≤ 105).

The fourth line contains m positive integers — the numbers to fill gaps. Each number is a positive integer not exceeding 109. Some numbers may be equal.

第一行包含一个整数 $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$ 的正整数。其中某些数字可能相等。

Print n space-separated numbers in a single line — the resulting sequence. If there are multiple possible answers, print any of them.

在一行中输出 n 个空格分隔的数字——即所得序列。若存在多个可能的答案，输出其中任意一个即可。

In the first sample there are no gaps, so the correct answer is the initial sequence.

In the second sample there is only one way to get an increasing subsequence of length 3.

In the third sample answer "4 2" would also be correct. Note that only strictly increasing subsequences are considered.

In the fifth sample the answer "1 1 1 2" is not considered correct, as number 1 can be used in replacing only two times.

在第一个样例中没有空缺，因此正确答案是初始序列。

在第二个样例中，仅有一种方式能得到长度为 3 的递增子序列。

在第三个样例中，答案 “4 2” 同样是正确的。注意：此处仅考虑严格递增的子序列。

在第五个样例中，答案 “1 1 1 2” 不被视为正确，因为数字 1 在替换中最多只能使用两次。