长度 $$$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]$$$。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,输出通过一次操作可以获得的按字典顺序排列的最大排列。
示例
输入复制
443 2 1 433 1 244 3 2 122 1
输出复制
4 1 2 33 2 14 3 2 12 1
注意
对于第一个测试用例,最佳段是 $$$[1, 4]$$$。反转后,$$$a = [4, 1, 2, 3]$$$。对于第二个测试用例,最佳段是 $$$[2, 3]$$$。反转后,$$$a = [3, 2, 1]$$$。