双端队列构造字典序最小排列

• 时间限制：1.0 s
• 内存限制：512.0 MB

题目描述

给定一个长度为 $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$ 添加到队首后，队列变为 $[4, 1, 5, 2]$；将同一个元素添加到队尾后，队列变为 $[1, 5, 2, 4]$。

排列中的元素依次被加入到初始为空的双端队列中，顺序从 $p_1$ 到 $p_n$。在每次加入元素之前，你可以选择将其加入到队首或队尾。

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

1. 将 $3$ 加入队尾：队列为 $[3]$；
2. 将 $1$ 加入队首：队列为 $[1, 3]$；
3. 将 $2$ 加入队尾：队列为 $[1, 3, 2]$；
4. 将 $4$ 加入队尾：队列为 $[1, 3, 2, 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 < y_i$。换句话说，如果序列 $x$ 和 $y$ 有一段（可能为空）前缀相同，且下一个元素 $x$ 比 $y$ 的对应元素小，则 $x$ 的字典序更小。例如，序列 $[1, 3, 2, 4]$ 的字典序小于 $[1, 3, 4, 2]$，因为前两个元素 $[1, 3]$ 相同，第三个元素 $2 < 4$。

输入格式

第一行包含一个整数 $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$。

输出格式

输出 $t$ 行，每行对应一个测试用例的答案。每个答案应包含 $n$ 个用空格分隔的整数，表示通过上述算法得到的字典序最小的排列。

输入输出样例

输入样例 #1

5
4
3 1 2 4
3
3 2 1
3
3 1 2
2
1 2
2
2 1

输出样例 #1

1 3 2 4
1 2 3
1 3 2
1 2
1 2

样例 1 解释

从排列 $[3, 1, 2, 4]$ 得到字典序最小排列 $[1, 3, 2, 4]$ 的一种方式已在题目描述中给出。

数据范围

• $1 \le t \le 1000$
• $1 \le n \le 2 \cdot 10^5$
• 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。