← 返回题目列表

Codeforces · 2193/B

B. 反转排列

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

长度 $$$n$$$ 的排列是一个数组,由 $$$n$$$ 个从 $$$1$$$ 到 $$$n$$$ 的不同整数以任意顺序组成。例如,$$$[2,3,1,5,4]$$$ 是排列,但 $$$[1,2,2]$$$ 和 $$$[1,3,4]$$$ 不是排列。

给你一个长度为 $$$n$$$ 的排列 $$$p$$$。您可以执行以下操作 正好一次:

  • 选择两个整数 $$$l,$$$ $$$r$$$ ($$$1\le l\le r\le n$$$)。
  • 反转排列 $$$p$$$ 中的段 $$$[l, r]$$$。
你的任务是输出执行此操作可以获得的按字典顺序排列的最大排列。如果对于它们不同的第一个位置 $$$i$$$,排列 $$$a$$$ 在字典顺序上大于排列 $$$b$$$,则它保持 $$$a_i\gt b_i$$$。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含数字 $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 不同的整数 $$$p_1, p_2,...,p_n$$$ $$$(1\le p_i\le n)$$$。

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

输出

对于每个测试用例,输出通过一次操作可以获得的按字典顺序排列的最大排列。

示例

输入
复制

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

输出
复制

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

注意

对于第一个测试用例,最佳段是 $$$[1, 4]$$$。反转后,$$$a = [4, 1, 2, 3]$$$。对于第二个测试用例,最佳段是 $$$[2, 3]$$$。反转后,$$$a = [3, 2, 1]$$$。