406984: GYM102646 B Combining Arrays

Timmy has two arrays $$$A$$$ and $$$B$$$, both of length $$$n$$$. It is guaranteed that when $$$A$$$ and $$$B$$$ are concatenated, they form a permutation of the numbers $$$1 \dots 2n$$$. He wants to create a new array $$$C$$$ by performing the following operation $$$2n$$$ times: choose either $$$A$$$ or $$$B$$$ if it still has elements, remove the element at the beginning of the chosen array, and append that element to the end of $$$C$$$. Of all ways that Timmy can create an array $$$C$$$ with these operations, he wants to find the lexicographically minimal possible one.

An array $$$a$$$ is lexicographically less than an array $$$b$$$ if, at the first position where $$$a$$$ and $$$b$$$ differ, the element of $$$a$$$ in this position is less than the element of $$$b$$$ in this position.

The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$. The second line contains $$$n$$$ space-separated integers $$$A_1, A_2, \dots, A_n$$$. The third line contains $$$n$$$ space-separated integers $$$B_1, B_2, \dots, B_n$$$.

Print $$$2n$$$ space-separated integers, the elements of the lexicographically minimal $$$C$$$.

3
1 2 3
4 5 6

1 2 3 4 5 6 

5
1 3 5 7 9
2 4 6 8 10

1 2 3 4 5 6 7 8 9 10 

7
6 10 4 2 13 12 7
9 8 11 3 5 1 14

6 9 8 10 4 2 11 3 5 1 13 12 7 14 

For the first sample, Timmy can first take $$$1, 2, $$$ and $$$3$$$ from $$$A$$$. Since $$$A$$$ is now empty, you must take $$$4, 5, $$$ and $$$6$$$ from $$$B$$$.

For the second sample, Timmy can alternate taking from $$$A$$$ and $$$B$$$.