P1078何处是归途（path）

【题目背景】

抄本离开晨汐港后，通向铜炉山的旧路却失去了清晰的指引。为了让车队继续前进，Ehundategh 来到废弃的路标台前，准备根据仅存的安装记录恢复归途。

【题目描述】

路标台中共有 $n$ 枚编号互不相同的路标，编号恰好为 $1\sim n$。台中的机械轨道会依次接收路标，并按照下面的规则形成一棵二叉查找树：

• 安装第一枚路标时，这枚路标成为树根。
• 安装编号为 $x$ 的路标时，机械轨道从树根开始寻找。若 $x$ 小于当前路标的编号，则进入左子树，否则进入右子树，直到遇到一个空位置，再将路标安装在这里。

Ehundategh 找到了一份安装顺序 $a_1,a_2,\ldots,a_n$。不同的安装顺序可能使路标台形成完全相同的二叉查找树，其中“完全相同”要求每个编号的路标具有相同的父亲、左儿子与右儿子。

重新安装时，Ehundategh 希望在每个能够选择的时刻优先处理编号较小的路标。对于两个不同的长度为 $n$ 的排列，找到它们第一个不同的位置，较小的数所在的排列具有更小的字典序。

请你求出所有能够恢复同一棵二叉查找树的安装顺序中字典序最小的一种，称为这座路标台的复原顺序。

形式化题意：给定 $1\sim n$ 的排列 $a$，求所有与 $a$ 构造出相同二叉查找树的排列中字典序最小的一个。

【输入格式】

从文件 $\textbf{\textit{path.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据的组数。$c=0$ 表示该测试点为样例。

对于每组测试数据：

第一行包含一个正整数 $n$，表示路标数量。

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示现存记录中的安装顺序。保证 $a$ 是 $1\sim n$ 的一个排列。

【输出格式】

输出到文件 $\textbf{\textit{path.out}}$ 中。

对于每组测试数据输出一行 $n$ 个正整数，表示对应二叉查找树的复原顺序。

【样例 1 输入】

10 22634 2 1 3 6 54755 3 7 2 4 6 1

【样例 1 输出】

14 2 1 3 6 525 3 2 1 4 7 6

【说明/提示】

【样例 1 解释】

在第二组测试数据中，安装 $5$ 后必须先安装左子树的树根 $3$ 或右子树的树根 $7$。由于 $3<7$，先复原左子树能够得到更小的字典序，继续按照相同原则处理即可得到样例输出。

【样例 2】

见选手目录下的 $\textbf{\textit{path/path2.in}}$ 和 $\textbf{\textit{path/path2.ans}}$。

该组样例符合测试点 $1\sim 4$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{path/path3.in}}$ 和 $\textbf{\textit{path/path3.ans}}$。

该组样例符合测试点 $5\sim 9$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{path/path4.in}}$ 和 $\textbf{\textit{path/path4.ans}}$。

该组样例符合测试点 $10\sim 15$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{path/path5.in}}$ 和 $\textbf{\textit{path/path5.ans}}$。

该组样例符合测试点 $16\sim 20$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq 20$，$1\leq n\leq 2\times 10^5$。对于同一个测试点，保证 $\sum n\leq 2\times 10^5$。

特殊性质：保证按照给出的安装顺序构成的二叉查找树高度不超过 $50$。