CF1579E1.Permutation Minimization by Deque

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 \lt 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.

事实上，题目 E1 和 E2 并没有太多共同之处。你应当将它们视作两个相互独立的问题。

给定一个长度为 $n$ 的排列 $p$。长度为 $n$ 的排列是指一个长度为 $n$ 的数组，其中恰好包含从 $1$ 到 $n$ 的每个整数各一次。例如，$[1, 4, 3, 2]$ 和 $[4, 2, 1, 3]$ 是合法的排列，而 $[1, 2, 4]$ 和 $[1, 2, 2]$ 则不是。

我们考虑一个初始为空的双端队列（deque）。双端队列是一种支持在首尾两端均插入元素的数据结构。例如，若当前双端队列中已有元素 $[1, 5, 2]$，则将元素 $4$ 插入队首会得到序列 $[\color{red}{4}, 1, 5, 2]$，而将其插入队尾则会得到 $[1, 5, 2, \color{red}{4}]$。

现将排列 $p$ 的元素依次加入初始为空的双端队列，即从 $p_1$ 开始，到 $p_n$ 结束。在将每个元素加入双端队列之前，你可以选择将其添加至队首或队尾。

例如，对于排列 $p = [3, 1, 2, 4]$，一种可能的操作序列如下：

$\quad$ 1.
将 $3$ 添加至双端队列尾部：
此时双端队列中的序列为 $[\color{red}{3}]$；

$\quad$ 2.
将 $1$ 添加至双端队列首部：
此时双端队列中的序列为 $[\color{red}{1}, 3]$；

$\quad$ 3.
将 $2$ 添加至双端队列尾部：
此时双端队列中的序列为 $[1, 3, \color{red}{2}]$；

$\quad$ 4.
将 $4$ 添加至双端队列尾部：
此时双端队列中的序列为 $[1, 3, 2, \color{red}{4}]$；

请找出在处理完整个排列后，双端队列中可能得到的字典序最小的元素序列。

序列 $[x_1, x_2, \ldots, x_n]$ 在字典序上小于序列 $[y_1, y_2, \ldots, y_n]$，当且仅当存在某个 $i \leq n$，使得 $x_1 = y_1$, $x_2 = y_2$, $\ldots$, $x_{i - 1} = y_{i - 1}$，且 $x_i \lt y_i$。换言之，若序列 $x$ 与 $y$ 具有某个（可能为空）的公共前缀，且序列 $x$ 在该前缀之后的首个元素严格小于序列 $y$ 中对应位置的元素。例如，序列 $[1, 3, 2, 4]$ 小于序列 $[1, 3, 4, 2]$，因为二者开头有两个匹配元素 $[1, 3]$，而第一个序列接下来的元素 $2$ 小于第二个序列对应位置的元素 $4$。

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$.

第一行包含一个整数 $t$（$1 \leq t \leq 1000$）—— 测试用例的数量。

接下来的 $2t$ 行包含各测试用例的描述。

每个测试用例描述的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 排列的长度。描述的第二行包含 $n$ 个以空格分隔的整数 $p_i$（$1 \le p_i \le n$；所有 $p_i$ 互不相同）—— 排列的元素。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

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.

输出 $t$ 行，每行包含对应测试用例的答案。每个测试用例的答案应包含 $n$ 个以空格分隔的整数——即执行上述算法后，在双端队列（deque）中可能得到的字典序最小的排列的各个元素。

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.

从排列 $[3, 1, 2, 4]$（第一个样例测试用例）得到字典序最小的排列 $[1, 3, 2, 4]$ 的一种方法已在题目描述中给出。