Neutral Tonality
Contest: Codeforces Round 908 (Div. 1)
Difficulty rating: 1700
Tags: constructive algorithms, greedy, sortings, two pointers

You are given an array $$$a$$$ consisting of $$$n$$$ integers, as well as an array $$$b$$$ consisting of $$$m$$$ integers.

Let $$$\text{LIS}(c)$$$ denote the length of the longest increasing subsequence of array $$$c$$$. For example, $$$\text{LIS}([2, \underline{1}, 1, \underline{3}])$$$ = $$$2$$$, $$$\text{LIS}([\underline{1}, \underline{7}, \underline{9}])$$$ = $$$3$$$, $$$\text{LIS}([3, \underline{1}, \underline{2}, \underline{4}])$$$ = $$$3$$$.

You need to insert the numbers $$$b_1, b_2, \ldots, b_m$$$ into the array $$$a$$$, at any positions, in any order. Let the resulting array be $$$c_1, c_2, \ldots, c_{n+m}$$$. You need to choose the positions for insertion in order to minimize $$$\text{LIS}(c)$$$.

Formally, you need to find an array $$$c_1, c_2, \ldots, c_{n+m}$$$ that simultaneously satisfies the following conditions:

- The array $$$a_1, a_2, \ldots, a_n$$$ is a subsequence of the array $$$c_1, c_2, \ldots, c_{n+m}$$$.
- The array $$$c_1, c_2, \ldots, c_{n+m}$$$ consists of the numbers $$$a_1, a_2, \ldots, a_n, b_1, b_2, \ldots, b_m$$$, possibly rearranged.
- The value of $$$\text{LIS}(c)$$$ is the minimum possible among all suitable arrays $$$c$$$.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n, m$$$ $$$(1 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5)$$$ — the length of array $$$a$$$ and the length of array $$$b$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$ — the elements of the array $$$a$$$.

The third line of each test case contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ $$$(1 \leq b_i \leq 10^9)$$$ — the elements of the array $$$b$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, output $$$n + m$$$ numbers — the elements of the final array $$$c_1, c_2, \ldots, c_{n+m}$$$, obtained after the insertion, such that the value of $$$\text{LIS}(c)$$$ is minimized. If there are several answers, you can output any of them.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first test case, $$$\text{LIS}(a) = \text{LIS}([6, 4]) = 1$$$. We can insert the number $$$5$$$ between $$$6$$$ and $$$4$$$, then $$$\text{LIS}(c) = \text{LIS}([6, 5, 4]) = 1$$$.

In the second test case, $$$\text{LIS}([\underline{1}, 7, \underline{2}, \underline{4}, \underline{5}])$$$ = $$$4$$$. After the insertion, $$$c = [1, 1, 7, 7, 2, 2, 4, 4, 5, 5]$$$. It is easy to see that $$$\text{LIS}(c) = 4$$$. It can be shown that it is impossible to achieve $$$\text{LIS}(c)$$$ less than $$$4$$$.

Example input:
7
2 1
6 4
5
5 5
1 7 2 4 5
5 4 1 2 7
1 9
7
1 2 3 4 5 6 7 8 9
3 2
1 3 5
2 4
10 5
1 9 2 3 8 1 4 7 2 9
7 8 5 4 6
2 1
2 2
1
6 1
1 1 1 1 1 1
777

Example output:
6 5 4
1 1 7 7 2 2 4 4 5 5
9 8 7 7 6 5 4 3 2 1
1 3 5 2 4
1 9 2 3 8 8 1 4 4 7 7 2 9 6 5
2 2 1
777 1 1 1 1 1 1

Editorial:
First observation: $$$\text{LIS}(c) \geq \text{LIS}(a)$$$. This is true because the array $$$c$$$ will always contain $$$a$$$ as a subsequence, and therefore any subsequence of $$$a$$$ as well.
Notice that it is always possible to achieve $$$\text{LIS}(c) \leq \text{LIS}(a) + 1$$$. Let $$$b_1 \geq \ldots \geq b_m$$$. This can be achieved by inserting $$$b_1, \ldots, b_m$$$ in a non-increasing order at any positions in the array $$$a$$$, because in this case, any increasing subsequence of $$$c$$$ can have at most one element from the array $$$b$$$, which means $$$\text{LIS}(c) \leq \text{LIS}(a) + 1$$$.
Therefore, we need to understand when we can achieve $$$\text{LIS}(c) = \text{LIS}(a)$$$. It turns out that this can always be achieved!
Let's understand how to insert one number ($$$x$$$) into the array while preserving $$$\text{LIS}(a)$$$. If $$$x < \min(a_1, \ldots, a_n)$$$, then we insert $$$x$$$ at the end of the array $$$a$$$, so that $$$x$$$ cannot be present in any increasing subsequence of length at least $$$2$$$, and $$$\text{LIS}(a)$$$ will not increase. Otherwise, we can insert $$$x$$$ before the first index $$$i$$$ such that $$$x \geq a_i$$$. Then, both $$$x$$$ and $$$a_i$$$ cannot be present in the same increasing subsequence. However, in any increasing subsequence where $$$x$$$ is present, we can replace $$$x$$$ with $$$a_i$$$ and the subsequence will still remain increasing. Thus, $$$\text{LIS}(a)$$$ will not increase.
Now we can apply this solution $$$m$$$ times, inserting the numbers $$$b_1 \geq b_2 \geq \ldots \geq b_m$$$ one by one. The final algorithm turns out to be surprisingly simple and similar to the merge(a, b) function. Specifically, iterate on arrays $$$a$$$ and $$$b$$$ with two pointers, at each step adding the larger of the two numbers ($$$a_i$$$ or $$$b_j$$$) to the answer and moving the corresponding pointer.
Time complexity: $$$O(n + m \log m)$$$