AT_awtf2025_a.LIS Keeping Swaps

给你一个 $(1,2,\cdots,N)$ 的排列 $(P_1,P_2,\cdots,P_N)$。

你可以执行以下操作任意次：

• 选择一个整数 $i(1\le i\le N-1)$ 并交换 $P_i$ 和 $P_{i+1}$。需要满足以下两个条件：
  • 执行操作前 $P_i>P_{i+1}$。
  • 操作不会改变 $P$ 的最长上升子序列长度。

找出通过对 $P$ 执行若干次操作可以达成的字典序最小的排列。

多组数据。

$S=(S_1,S_2,\cdots,S_{\vert S\vert})$ 的字典序小于 $S=(T_1,T_2,\cdots,T_{\vert T\vert})$ 当且仅当以下两个条件之一被满足。在此 $\vert S\vert$ 和 $\vert T\vert$ 分别表示 $S$ 和 $T$ 的长度。

1. $\vert S\vert <\vert T\vert$ 且 $(S_1,S_2,\cdots,S_{\vert S\vert})=(T_1,T_2,\cdots,T_{\vert S\vert})$。
2. 存在一个整数 $1\le i\le \min\{\vert S\vert,\vert T\vert\}$ 满足：
   • $(S_1,S_2,\cdots,S_{i-1})=(T_1,T_2,\cdots,T_{i-1})$。
   • $S_i<T_i$。

第一行一个整数 $T(1\le T\le 2.5\times 10^5)$，表示数据组数。

对于每组数据，第一行一个整数 $N(1\le N\le 2.5\times 10^5)$。

第二行 $N$ 个整数 $P_1,P_2,\cdots,P_N(1\le P_i\le N)$，为一个 $1$ 到 $N$ 的排列。

保证单个测试点中 $N$ 的和不超过 $2.5\times 10^5$。

对于每组数据，输出一行一个整数表示答案。

样例解释

对于第一组数据，$P=(2,3,1)$ 不能执行 $i=1$ 的操作，但是可以执行 $i=2$ 的操作，之后 $P=(2,1,3)$，不能执行任何操作。在所有 $P=(2,3,1)$ 通过若干次操作达到的排列中，$P=(2,1,3)$ 是字典序最小的。