题目描述

给你一个长度为 $n$ 的排列 $p$。在位置 $x$ 和 $y$（$x < y$）各有一个传送门。

位置 $i$ 的传送门最初位于数组第 $i$ 个和第 $(i+1)$ 个元素之间。特别地，如果 $i=0$，传送门位于第一个元素之前；如果 $i=n$，传送门位于最后一个元素之后。

你可以无限次执行以下两种操作中的一种：

1. 将某个传送门左侧紧邻的元素移除，并将其插入到另一个传送门右侧紧邻处。
2. 将某个传送门右侧紧邻的元素移除，并将其插入到另一个传送门左侧紧邻处。

令 $\mathbf{\color{red}{\mathcal{O}}}$ 表示传送门。例如，若 $p = [3,\mathbf{\color{red}{\mathcal{O}}},2,4,\mathbf{\color{red}{\mathcal{O}}},1]$：

• 分别在左、右传送门使用操作 1，得到数组 $[\mathbf{\color{red}{\mathcal{O}}},2,4,\mathbf{\color{red}{\mathcal{O}}},3,1]$ 和 $[3,\mathbf{\color{red}{\mathcal{O}}},4,2,\mathbf{\color{red}{\mathcal{O}}},1]$。
• 分别在左、右传送门使用操作 2，得到数组 $[3,\mathbf{\color{red}{\mathcal{O}}},4,2,\mathbf{\color{red}{\mathcal{O}}},1]$ 和 $[3,1,\mathbf{\color{red}{\mathcal{O}}},2,4,\mathbf{\color{red}{\mathcal{O}}}]$。

请找出你能够通过这些操作得到的排列中字典序最小的一个。注意，传送门在字典序比较中没有影响。

$^{\text{∗}}$ 长度为 $n$ 的排列是一个长度为 $n$ 的数组，包含 $1$ 到 $n$ 的每个整数各一次。

$^{\text{†}}$ 如果存在下标 $i$ 使得对于所有 $1 \leq j < i$ 都有 $a_j = b_j$，且 $a_i < b_i$，则排列 $a$ 字典序小于排列 $b$。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 2\cdot 10^4$），表示测试用例个数。

每个测试用例的第一行包含三个整数 $n$、$x$、$y$（$1 \leq n \leq 2 \cdot 10^5$，$0 \leq x < y \leq n$）。

每个测试用例的第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$，表示一个长度为 $n$ 的排列。

所有测试用例中的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行 $n$ 个整数，表示你可以得到的字典序最小的排列。

样例

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

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

样例说明

令 $\mathbf{\color{red}{\mathcal{O}}}$ 表示传送门。

在第一个测试用例中，数组为 $[\mathbf{\color{red}{\mathcal{O}}},3,1,4,2,\mathbf{\color{red}{\mathcal{O}}}]$。在左侧传送门使用操作 2 得到 $[\mathbf{\color{red}{\mathcal{O}}},1,4,2,3,\mathbf{\color{red}{\mathcal{O}}}]$，这是能得到的字典序最小的排列。

上述为描述中的操作动画。

在第二个测试用例中，数组为 $[3,\mathbf{\color{red}{\mathcal{O}}},2,\mathbf{\color{red}{\mathcal{O}}},1]$，在左侧传送门使用操作 1 得到 $[\mathbf{\color{red}{\mathcal{O}}},2,\mathbf{\color{red}{\mathcal{O}}},3,1]$，这是能得到的字典序最小的排列。

在第四个测试用例中，最优方案是不进行任何操作。

由 ChatGPT 5 翻译

来源

Codeforces 2200D，英文题名 Portal。