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

第一行一个整数 $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)$ 是字典序最小的。