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.

N/A

N/A

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.