Reverse a Permutation

Lexicographic maximization cares about the earliest position first. Later positions are background noise until the first difference is settled.

The absolute lexicographically maximum permutation of length $n$ is

$$[n, n-1, n-2, \dots, 1].$$

We cannot arbitrarily rearrange the array, but we can choose one segment and reverse it. So we scan from left to right and keep asking: is this position already as large as it possibly can be?

At position $i$ using $1$-indexed notation, if all previous positions are already optimal, then the largest remaining value is

$$n-i+1.$$

If $p_i = n-i+1$, great. That position is perfect. Any reversal that changes it would put a smaller value there, making the whole permutation lexicographically worse. So we leave it alone and move on.

Now suppose $i$ is the first position where

$$p_i \ne n-i+1.$$

All values larger than $n-i+1$ must already appear in positions $1,2,\dots,i-1$, because those positions matched the descending maximum prefix. Therefore the best possible value for position $i$ is exactly $n-i+1$.

Where can that value come from? Since $p$ is a permutation, it appears at one unique position $j > i$. To move $p_j$ into position $i$ using one reversal, the segment must start at $i$ and end at $j$:

$$[l,r] = [i,j].$$

After reversing this segment, $p_j = n-i+1$ becomes the new value at position $i$. This gives the largest possible prefix, and lexicographic order says that is all that matters. No fancy suffix optimization can compensate for losing earlier. That's the whole trick; don't overthink it.

If the scan never finds such an $i$, then the permutation is already

$$[n,n-1,\dots,1],$$

which is lexicographically maximum among all permutations. Since the operation must be performed exactly once, we can choose a segment of length $1$, which changes nothing.

Algorithm:

1. Store the position of every value.
2. Scan $i=1$ to $n$.
3. Find the first $i$ where $p_i \ne n-i+1$.
4. Let $j$ be the position of $n-i+1$.
5. Reverse $p_i, p_{i+1}, \dots, p_j$.
6. Output the result.

Proof of correctness:

Consider the first index $i$ where the original permutation differs from the descending permutation. For every $k<i$, we have $p_k=n-k+1$, the maximum possible value at that position after fixing all previous positions. Any reversal touching one of these positions would replace it with a smaller value, so the result would be lexicographically worse than simply preserving this prefix.

Thus an optimal reversal must start at or after $i$. If it starts after $i$, then position $i$ remains $p_i$, which is smaller than $n-i+1$. But $n-i+1$ is still available somewhere after $i$, so we can do better by moving it to position $i$.

The only reversal that moves the value $n-i+1$ to position $i$ is reversing the segment from $i$ to its current position. Therefore this move gives the maximum possible value at the first position where improvement is possible. Since lexicographic order is decided by the earliest differing position, this result is optimal.

If no such index exists, the permutation is already the descending permutation, which is globally lexicographically maximum. A length-$1$ reversal preserves it, so it is valid and optimal.

Complexity:

For each test case, building positions, scanning, and reversing take $O(n)$ time. The memory usage is $O(n)$. Across all test cases, the total time is $O\left(\sum n\right)$, which fits easily.