← 返回题目列表

Codeforces · 2200/D

D. 门户

中文机器翻译题面 查看原题

给你一个长度为 $$$n$$$ 的排列$$$^{\text{∗}}$$$ $$$p$$$。还有两个传送门位于位置 $$$x$$$ 和 $$$y$$$ ($$$x \lt 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{†}}$$$ 最小排列。请注意,门户不会影响排列的字典顺序比较。

$$$^{\text{*}}$$$长度 $$$n$$$ 的排列是长度为 $$$n$$$ 的数组,包含从 $$$1$$$ 到 $$$n$$$ 的每个整数恰好一次。

$$$^{\text{†}}$$$如果存在索引 $$$i$$$,则对于所有索引 $$$1 \leq j \lt i$$$ 和 $$$a_i \lt b_i$$$,$$$a_j = b_j$$$ 按字典顺序排列 $$$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 \lt 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]$$$,这是可以获得的按字典顺序排列的最小可能排列。

在第四个测试用例中,最好不进行任何操作。