Reflect Sort

Research cross-check: the official Codeforces problem page and tutorial PDF point to the invariant $|a_i-a_{i+1}|$ and the final gcd step; I also checked the Codeforces status page for an accepted C++23 submission and a Luogu explanation with the same formula. Sources: problem, official analysis PDF, status page, Luogu writeup.

Define

$d_i=a_{i+1}-a_i \qquad (1\le i<n).$

Look at what the operation does to these adjacent differences.

If we reflect the prefix $\{1,2,\dots,i-1\}$ around $a_i$, then every element before $i$ becomes $2a_i-a_j$. For every adjacent pair fully inside that prefix, the difference changes sign. The boundary difference also changes sign. So:

$d_1,d_2,\dots,d_{i-1}\text{ all flip sign.}$

If we reflect the suffix $\{i+1,i+2,\dots,n\}$ around $a_i$, then similarly:

$d_i,d_{i+1},\dots,d_{n-1}\text{ all flip sign.}$

So the important invariant is:

$|d_i|=|a_{i+1}-a_i|\text{ never changes.}$

That is the main trick. The actual values can fly through negative-land during operations, but the absolute adjacent gaps are locked in.

In the final array we need

$1\le a_1\le a_2\le\dots\le a_n.$

So every final adjacent difference must be nonnegative. Since its absolute value is fixed, the final difference must be exactly

$|a_{i+1}-a_i|.$

Therefore once the final value of $a_1$ is known, the final value of $a_n$ is forced:

$a_n=a_1+\sum_{i=1}^{n-1}|a_{i+1}-a_i|.$

So minimizing $a_n$ is the same as minimizing the final positive value of $a_1$. Nice. The sorting part was basically bait.

Now we determine which values of $a_1$ are reachable.

Let

$b_i=|a_{i+1}-a_i|,$

and let

$g=\gcd(2b_1,2b_2,\dots,2b_{n-1})=2\gcd(b_1,b_2,\dots,b_{n-1}).$

A suffix reflection never changes $a_1$. A prefix reflection around some $a_i$ changes $a_1$ into

$2a_i-a_1,$

so the change is

$2a_i-2a_1=2(a_i-a_1)=2\sum_{k=1}^{i-1}d_k.$

Each $d_k$ has absolute value $b_k$, so this change is always divisible by $g$. Thus:

$a_1 \bmod g$

is invariant, unless $g=0$.

Now we need the reverse direction: every multiple of $g$ is actually achievable. For any $x$, do these two prefix reflections:

1. reflect $\{1,\dots,x\}$ around $a_{x+1}$,
2. reflect $\{1,\dots,x-1\}$ around the current $a_x$.

This changes $a_1$ by

$2(a_{x+1}-a_x)=2d_x,$

up to sign. Suffix operations can flip signs of differences without touching $a_1$, so we can add or subtract $2b_x$ whenever we want. By Bezout's identity, all integer combinations of $2b_i$ are exactly the multiples of $g$.

So the reachable values of $a_1$ are exactly:

$a_1 + kg \qquad (k\in\mathbb Z).$

We need the smallest positive number in this congruence class. If $g>0$, that value is

$r=((a_1-1)\bmod g)+1.$

This gives a value in $[1,g]$ and preserves the same residue modulo $g$. If $g=0$, then every adjacent gap is $0$, all elements are equal, and no operation changes anything useful; the answer is just the original $a_1$.

Finally:

$\boxed{\text{answer}=r+\sum_{i=1}^{n-1}|a_{i+1}-a_i|}.$

After setting $a_1=r$, suffix flips can make every $d_i$ nonnegative without changing $a_1$: scan left to right, and whenever the current difference is negative, flip the suffix starting there. So the construction exists; this is not just some modulo fanfiction.

Edge cases:

• If all numbers are equal, then $g=0$ and the answer is $a_1$.
• Differences equal to $0$ do not affect the gcd or the sum.
• The sum can be about $10^{14}$, so use long long.

Complexity:

We do one pass over the array and compute gcds.

$O(n\log A)$

time and $O(1)$ extra memory, where $A\le 10^9$.