Flipper
Contest: Codeforces Round 874 (Div. 3)
Difficulty rating: 1400
Tags: brute force, constructive algorithms, greedy

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 < i$$$ and $$$a_i > b_i$$$.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
9
5
2 3 1 5 4
9
4 1 6 7 2 8 5 3 9
4
4 3 2 1
2
2 1
6
3 2 4 1 5 6
7
3 2 1 5 7 6 4
10
10 2 5 6 1 9 3 8 4 7
4
4 2 1 3
1
1

Example output:
5 4 1 3 2 
9 4 1 6 7 2 8 5 3 
3 2 1 4 
1 2 
6 5 3 2 4 1 
7 6 4 5 3 2 1 
9 3 8 4 7 1 10 2 5 6 
3 4 2 1 
1

Editorial:
In these constraints we could solve the problem for $$$O(n^2)$$$. Let us note that there can be no more than two candidates for the value $$$r$$$. Since the first number in the permutation will be either $$$p_{r+1}$$$ if $$$r < n$$$, or $$$p_r$$$ if $$$r = n$$$. Then let's go through the value of $$$r$$$ and choose the one in which the first number in the resulting permutation is as large as possible. Next, if $$$p_n = n$$$, then we can have two candidates for $$$r$$$ is $$$n, n-1$$$, but note that it is always advantageous to put $$$r = n$$$ in that case, since it will not spoil the answer. Then we can go through $$$l$$$ and get the solution by the square, but we can do something smarter.
Notice now that the answer already contains all the numbers $$$p_i$$$ where $$$i > r$$$. And then we write $$$p_r, p_{r-1}, \ldots, p_l$$$ where $$$l$$$ is still unknown, and then $$$p_1, p_2, \ldots, p_{l-1}$$$. In that case, let's write $$$p_r$$$ as $$$l \le r$$$ and then write $$$p_{r-1}, p_{r-2}, \ldots$$$ as long as they are larger than $$$p_1$$$. Otherwise, we immediately determine the value of $$$l$$$ and finish the answer to the end. Thus, constructively we construct the maximal permutation.