CF1833D.Flipper

You are given a permutation $p$ of length $n$.

A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in any order. For example, ${2,3,1,5,4}$ is a permutation, while ${1,2,2}$ is not (since $2$ appears twice), and ${1,3,4}$ is also not a permutation (as $n=3$, but the array contains $4$).

To the permutation $p$, you need to apply the following operation exactly once:

• First you choose a segment $[l, r]$ ($1 \le l \le r \le n$, a segment is a continuous sequence of numbers ${p_l, p_{l+1}, \ldots, p_{r-1}, p_r}$) and reverse it. Reversing a segment means swapping pairs of numbers $(p_l, p_r)$, $(p_{l+1}, p_{r-1})$, ..., $(p_{l + i}, p_{r - i})$ (where $l + i \le r - i$).
• Then you swap the prefix and suffix: $[r+1, n]$ and $[1, l - 1]$ (note that these segments may be empty).

For example, given $n = 5, p = {2, \color{blue}{3}, \color{blue}{1}, 5, 4}$, if you choose the segment $[l = 2, r = 3]$, after reversing the segment $p = {\color{green}{2}, \color{blue}{1}, \color{blue}{3}, \color{green}{5}, \color{green}{4}}$, then you swap the segments $[4, 5]$ and $[1, 1]$. Thus, $p = {\color{green}{5}, \color{green}{4}, 1, 3, \color{green}{2}}$. It can be shown that this is the maximum possible result for the given permutation.

You need to output the lexicographically maximum permutation that can be obtained by applying the operation described exactly once.

A permutation $a$ is lexicographically greater than permutation $b$ if there exists an $i$ ($1 \le i \le n$) such that $a_j = b_j$ for $1 \le j \lt i$ and $a_i \gt b_i$.

给你一个长度为 $n$ 的排列 $p$。

排列是由 $1$ 到 $n$ 中互不相同的 $n$ 个整数以任意顺序组成的数组。例如，${2,3,1,5,4}$ 是一个排列，而 ${1,2,2}$ 不是（因为 $2$ 出现了两次），${1,3,4}$ 也不是排列（因为 $n=3$，但数组中包含了 $4$）。

你需要对排列 $p$ 恰好执行一次如下操作：

• 首先，你选择一个区间 $[l, r]$（其中 $1 \le l \le r \le n$；该区间表示连续的子序列 ${p_l, p_{l+1}, \ldots, p_{r-1}, p_r}$），并将其翻转。翻转区间意味着交换数对 $(p_l, p_r)$、$(p_{l+1}, p_{r-1})$、……、$(p_{l + i}, p_{r - i})$（其中满足 $l + i \le r - i$）。
• 然后，你交换前缀与后缀：即区间 $[r+1, n]$ 与 $[1, l - 1]$（注意：这两个区间可能为空）。

例如，给定 $n = 5$，$p = {2, \color{blue}{3}, \color{blue}{1}, 5, 4}$，若你选择区间 $[l = 2, r = 3]$，则翻转该区间后得到 $p = {\color{green}{2}, \color{blue}{1}, \color{blue}{3}, \color{green}{5}, \color{green}{4}}$；接着交换区间 $[4, 5]$ 与 $[1, 1]$，最终得到 $p = {\color{green}{5}, \color{green}{4}, 1, 3, \color{green}{2}}$。可以证明，这是对给定排列所能得到的最大结果。

你需要输出通过恰好执行一次上述操作所能得到的字典序最大的排列。

排列 $a$ 字典序大于排列 $b$，当且仅当存在某个下标 $i$（$1 \le i \le n$），使得对所有 $1 \le j < i$ 都有 $a_j = b_j$，且 $a_i > b_i$。

The first line of the input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

Then the descriptions of the test cases follow.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2000$) — the size of the permutation.

The second line of each test case contains $n$ integers: $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) — the permutation $p$ itself.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.

输入的第一行包含一个整数 $t$（$1 \le t \le 1000$）——测试用例的数量。

随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2000$）——排列的长度。

每个测试用例的第二行包含 $n$ 个整数：$p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$）——排列 $p$ 本身。

保证所有测试用例的 $n$ 之和不超过 $2000$。

For each test case, output in a separate line the lexicographically maximum permutation of length $n$ that can be obtained from $p$ by applying the operation described in the problem exactly once.

对于每个测试用例，在单独一行中输出通过对排列 $p$ 恰好执行一次题目中描述的操作所能得到的长度为 $n$ 的字典序最大的排列。

The first example is explained in the problem statement.

In the second example, the segment $[l = 9, r = 9]$ should be chosen.

In the third example, the segment $[l = 1, r = 1]$ should be chosen.

In the fourth example, the segment $[l = 1, r = 2]$ should be chosen.

In the fifth example, the segment $[l = 5, r = 6]$ should be chosen.

In the sixth example, the segment $[l = 4, r = 4]$ should be chosen.

In the seventh example, the segment $[l = 5, r = 5]$ should be chosen.

第一个示例在题目描述中已作解释。

第二个示例中，应选择区间 $[l = 9, r = 9]$。

第三个示例中，应选择区间 $[l = 1, r = 1]$。

第四个示例中，应选择区间 $[l = 1, r = 2]$。

第五个示例中，应选择区间 $[l = 5, r = 6]$。

第六个示例中，应选择区间 $[l = 4, r = 4]$。

第七个示例中，应选择区间 $[l = 5, r = 5]$。