Permutation Minimization by Deque
Contest: Codeforces Round 744 (Div. 3)
Difficulty rating: 1000
Tags: constructive algorithms, greedy, math

In fact, the problems E1 and E2 do not have much in common. You should probably think of them as two separate problems.

A permutation $$$p$$$ of size $$$n$$$ is given. A permutation of size $$$n$$$ is an array of size $$$n$$$ in which each integer from $$$1$$$ to $$$n$$$ occurs exactly once. For example, $$$[1, 4, 3, 2]$$$ and $$$[4, 2, 1, 3]$$$ are correct permutations while $$$[1, 2, 4]$$$ and $$$[1, 2, 2]$$$ are not.

Let us consider an empty deque (double-ended queue). A deque is a data structure that supports adding elements to both the beginning and the end. So, if there are elements $$$[1, 5, 2]$$$ currently in the deque, adding an element $$$4$$$ to the beginning will produce the sequence $$$[\color{red}{4}, 1, 5, 2]$$$, and adding same element to the end will produce $$$[1, 5, 2, \color{red}{4}]$$$.

The elements of the permutation are sequentially added to the initially empty deque, starting with $$$p_1$$$ and finishing with $$$p_n$$$. Before adding each element to the deque, you may choose whether to add it to the beginning or the end.

For example, if we consider a permutation $$$p = [3, 1, 2, 4]$$$, one of the possible sequences of actions looks like this: $$$\quad$$$ 1.add $$$3$$$ to the end of the deque:deque has a sequence $$$[\color{red}{3}]$$$ in it;$$$\quad$$$ 2.add $$$1$$$ to the beginning of the deque:deque has a sequence $$$[\color{red}{1}, 3]$$$ in it;$$$\quad$$$ 3.add $$$2$$$ to the end of the deque:deque has a sequence $$$[1, 3, \color{red}{2}]$$$ in it;$$$\quad$$$ 4.add $$$4$$$ to the end of the deque:deque has a sequence $$$[1, 3, 2, \color{red}{4}]$$$ in it;

Find the lexicographically smallest possible sequence of elements in the deque after the entire permutation has been processed.

A sequence $$$[x_1, x_2, \ldots, x_n]$$$ is lexicographically smaller than the sequence $$$[y_1, y_2, \ldots, y_n]$$$ if there exists such $$$i \leq n$$$ that $$$x_1 = y_1$$$, $$$x_2 = y_2$$$, $$$\ldots$$$, $$$x_{i - 1} = y_{i - 1}$$$ and $$$x_i < y_i$$$. In other words, if the sequences $$$x$$$ and $$$y$$$ have some (possibly empty) matching prefix, and the next element of the sequence $$$x$$$ is strictly smaller than the corresponding element of the sequence $$$y$$$. For example, the sequence $$$[1, 3, 2, 4]$$$ is smaller than the sequence $$$[1, 3, 4, 2]$$$ because after the two matching elements $$$[1, 3]$$$ in the start the first sequence has an element $$$2$$$ which is smaller than the corresponding element $$$4$$$ in the second sequence.

Input format:
The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

The next $$$2t$$$ lines contain descriptions of the test cases.

The first line of each test case description contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — permutation size. The second line of the description contains $$$n$$$ space-separated integers $$$p_i$$$ ($$$1 \le p_i \le n$$$; all $$$p_i$$$ are all unique) — elements of the permutation.

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

Output format:
Print $$$t$$$ lines, each line containing the answer to the corresponding test case. The answer to a test case should contain $$$n$$$ space-separated integer numbers — the elements of the lexicographically smallest permutation that is possible to find in the deque after executing the described algorithm.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
One of the ways to get a lexicographically smallest permutation $$$[1, 3, 2, 4]$$$ from the permutation $$$[3, 1, 2, 4]$$$ (the first sample test case) is described in the problem statement.

Example input:
5
4
3 1 2 4
3
3 2 1
3
3 1 2
2
1 2
2
2 1

Example output:
1 3 2 4 
1 2 3 
1 3 2 
1 2 
1 2

Editorial:
We'll process the permutation elements one by one.
For the first element, it doesn't matter which side of the deque we add it to, the result of its addition will be the same — there will be a sequence of one element (equal to the first permutation element) in the deque.
Now let's consider adding the $$$i$$$-th element of a permutation to the deque. First $$$i = 2$$$ will be considered, then $$$i = 3$$$, and so on up to $$$i = n$$$. Let us describe the general algorithm for choosing the side of the deque for each step. Note that if the elements $$$[d_1, \ldots, d_{i - 1}]$$$ are now in the deque, then all final permutations that can be obtained in the deque from the current state can be broken down into pairs of the form $$$$$$[\ldots, \color{red}{a_i}, \color{blue}{d_1, \ldots, d_{i - 1}}, \ldots]\,$$$$$$ $$$$$$[\ldots, \color{blue}{d_1, \ldots, d_{i - 1}}, \color{red}{a_i}, \ldots]\text{,}$$$$$$ where the beginning and the end of the final permutations, hidden behind "$$$\ldots$$$", are obtained by the same sequences of all the following choices and thus are equal between the first and the second.
Note that when $$$a_i < d_1$$$ the first permutation will always be lexicographically smaller than the second one, and vice versa. Therefore, regardless of the following choices, if $$$a_i < d_1$$$ then the second permutation will never be minimal, and if $$$a_i > d_1$$$ then the first permutation will never be minimal.
This means that we can make a choice about the side of the deque to add the $$$i$$$-th element to based only on its relation to $$$d_1$$$: if $$$a_i < d_1$$$, then $$$a_i$$$ is added to the beginning of the deque, otherwise — to the end.
The time complexity is $$$\mathcal{O}(n)$$$. Alternative solutions, which also fit in the time limit, involved finding a lexicographically minimal increasing sequence in the reversed original permutation and could be implemented either with $$$\mathcal{O}(n \log n)$$$ time complexity or with $$$\mathcal{O}(n)$$$ time complexity if the permutation's definition was taken into consideration.