CF2156F2.Strange Operation (Hard Version)

这是该问题的困难版本。本版本与其他版本的区别在于，这一版本中 $n$ 的约束更大。仅当你完成了该问题的所有版本时，才可以尝试 Hack。

给定一个长度为 $n$ 的排列 $p$ 。你可以进行如下操作任意多次（包括零次）：

• 选择三个互不相同的下标 $i$、$j$ 和 $k$（$1 \le i < j < k \le n$），使得下列两个条件同时成立：$p_i = \max(p_j, p_k) + 1$ 且 $p_i = \min(p_j, p_k) + 2$。然后，将 $p_i$ 减 $2$，将 $p_j$ 和 $p_k$ 各加 $1$。即 $p_i := p_i - 2$，$p_j := p_j + 1$，$p_k := p_k + 1$。

可以证明，由于 $p_i = \max(p_j, p_k) + 1$ 且 $p_i = \min(p_j, p_k) + 2$ 这两个条件的限制，每次操作后 $p$ 仍然是一个排列。

你的任务是，经过若干次操作后，求出能够获得的字典序最小的排列。

$^{\text{∗}}$ 长度为 $n$ 的排列是指包含 $n$ 个互不相同、从 $1$ 到 $n$ 的整数的一种排列。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是一个排列（$2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（$n=3$，但数组中出现了 $4$）。

$^{\text{†}}$ 如果两个长度相同的序列 $a$ 与 $b$ 满足：

• $a \ne b$，且在第一个不相等的位置，$a$ 的元素小于 $b$ 的元素，

则称 $a$ 的字典序小于 $b$。

本题包含多组测试数据。第一行为测试用例个数 $t$（$1 \le t \le 10^4$）。接下来的每组数据格式如下。

每组测试数据的第一行为一个整数 $n$（$3 \le n \le 3 \times 10^5$），表示排列的长度。

第二行为 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$），表示排列 $p$。

保证所有测试用例中 $n$ 的总和不超过 $3 \times 10^5$。

对于每组测试数据，输出一行 $n$ 个整数，表示通过若干次操作能够得到的字典序最小的排列。

在第一个测试用例中，最优策略是对 $i=1$，$j=2$，$k=3$ 执行一次操作。注意，不能对 $i=1$，$j=3$，$k=4$ 执行操作，因为必须同时满足两个条件。此处第二个条件 $p_1 = \min(p_3, p_4) + 2$ 成立，但第一个条件 $p_1 = \max(p_3, p_4) + 1$ 不成立。

在第二个测试用例中，可以依次进行以下操作：

• 选择 $i=1$，$j=4$，$k=5$，此时排列变为 $[1, 4, 5, 3, 2]$。
• 选择 $i=2$，$j=4$，$k=5$，排列变为 $[1, 2, 5, 4, 3]$。
• 选择 $i=3$，$j=4$，$k=5$，排列变为 $[1, 2, 3, 5, 4]$。

在第三个测试用例中，没有合法的 $i < j < k$ 使条件成立，因此无法进行任何操作。

由 ChatGPT 5 翻译