Restricted Sorting

Let $b$ be the sorted version of $a$, and let

$mn=\min(a), \qquad mx=\max(a).$

If $a$ is already sorted, the answer is $-1$. This is not a typo or sample weirdness: with zero operations, the array is sorted for every integer $k$, so there is no largest piggy integer. Infinite answers, no maximum. Annoying, but fair.

Now assume $a$ is not sorted.

For a fixed $k$, model each occurrence of a value as a token. Two tokens can be swapped directly if their values differ by at least $k$. Since swaps are arbitrary by position, the only thing that matters is the graph on values/occurrences where edges connect pairs with difference at least $k$.

A standard fact: transpositions along edges of a connected graph generate every permutation inside that connected component. So any value occurrence inside the same connected component can be rearranged however we want. Values outside that component are stuck with only whatever their own component can do.

The key is that this graph is very structured. Edges connect values that are far apart. If

$k \le mx-mn,$

then $mn$ and $mx$ are connected by an edge. They form the “main movable component.” A value $x$ belongs to this component if it can connect to either endpoint:

$x-mn \ge k \quad \text{or} \quad mx-x \ge k.$

Equivalently, $x$ is not in the movable component exactly when

$x-mn < k \quad \text{and} \quad mx-x < k.$

Those middle-ish values are too close to both extremes, so they cannot swap with anything useful. They are basically glued in place. Tough luck.

Now compare $a$ with $b$. If $a_i=b_i$, index $i$ is already fine; we do not need to move that occurrence. If $a_i \ne b_i$, then the value currently at index $i$ must leave this position during sorting. That is possible only if $a_i$ is in the movable component.

So for every misplaced value $a_i$, we need:

$a_i-mn \ge k \quad \text{or} \quad mx-a_i \ge k.$

That is the same as:

$k \le \max(a_i-mn,\ mx-a_i).$

Also, because the array is not already sorted, we need at least one real swap, so $k$ cannot exceed $mx-mn$; otherwise no two different values can ever be swapped. This is already covered by the same formula for extremes, but keeping it explicit makes the logic clean.

Therefore the largest valid $k$ is:

$\min_{i: a_i\ne b_i} \max(a_i-mn,\ mx-a_i).$

Why is this sufficient? For that $k$, every misplaced value belongs to the main component containing $mn$ and $mx$. Since all positions that need changes contain movable tokens, we can permute those movable occurrences arbitrarily. Fixed positions where $a_i=b_i$ can simply be left alone. Thus we can place the needed sorted values into all mismatched positions and obtain $b$.

Edge cases:

• If $n=1$, the array is sorted, so answer $-1$.
• If the array is already non-descending, answer $-1$.
• Duplicates are fine because comparing against sorted $b$ by value is enough; equal occurrences are interchangeable.
• Values are up to $10^9$, so int technically works for differences, but long long is harmless and avoids dumb overflow drama.

Complexity per test case is dominated by sorting:

$O(n\log n)$

with $O(n)$ extra memory.