At some point, let \(x_i\) be the coordinate of the \(i\)-th piece from the left \((1\leq i\leq N)\), and \(d_j = x_{j+1}-x_j\) be the distance between the \(j\)-th and \((j+1)\)-th pieces from the left \((1\leq j\leq N-1)\).
From this state, let us consider what happens if we choose an integer \(i_0\) (\(1 \leq i_0 \leq N-3\)) and perform the operation.
Only the \((i_0+1)\)-th and \((i_0+2)\)-th pieces (before the operation) move, as follows. - The \((i_0+1)\)-th piece from the left goes from \(x_{i_0+1}\) to \(2\times\frac{x_{i_0}+x_{i_0+3}}{2}-x_{i_0+1}=x_{i_0}+x_{i_0+3}-x_{i_0+1}\). - The \((i_0+2)\)-th piece from the left goes from \(x_{i_0+2}\) to \(2\times\frac{x_{i_0}+x_{i_0+3}}{2}-x_{i_0+2}=x_{i_0}+x_{i_0+3}-x_{i_0+2}\).

From \(x_{i_0}<x_{i_0+1}<x_{i_0+2}<x_{i_0+3}\), we have \(x_{i_0}<x_{i_0}+x_{i_0+3}-x_{i_0+2}<x_{i_0}+x_{i_0+3}-x_{i_0+1}<x_{i_0+3}\), so only these two pieces swap their relative order, and all other relative orderings remain the same.
Let \(d'_j\) be the distance between the \(j\)-th and \((j+1)\)-th pieces \((1\leq j\leq N-1)\) after the operation. We have \(d'_j=d_j\) for \(j\neq i_0,i_0+1,i_0+2\), and the following for \(j = d'_{i_0}, d'_{i_0+1}, d'_{i_0+2}\):

• \(d'_{i_0}=(x_{i_0}+x_{i_0+3}-x_{i_0+2})-x_{i_0}=d_{i_0+2}\)
• \(d'_{i_0+1}=(x_{i_0}+x_{i_0+3}-x_{i_0+1})-(x_{i_0}+x_{i_0+3}-x_{i_0+2})=d_{i_0+1}\)
• \(d'_{i_0+2}=x_{i_0+3}-(x_{i_0}+x_{i_0+3}-x_{i_0+1})=d_{i_0}\)

Therefore, This operation corresponds to swapping \(d_{i_0}\) and \(d_{i_0+2}\).
Thus, \((d_1,d_3,\ldots)\) is always a permutation of \((X_2-X_1, X_4-X_3, \ldots)\), and \((d_2,d_4,\ldots)\) is always a permutation of \((X_3-X_2, X_5-X_4, \ldots)\).
On the other hand, the operations affecting \((d_1, d_3, \dots)\) and \((d_2, d_4, \dots)\) are independent, and by repeated adjacent swaps, any permutation of these subsequences can be achieved.
Moreover, since the leftmost piece’s coordinate \(x_1\) never changes.
Therefore, the final configuration of piece coordinates from left to right after a series of operations must be described as \((X_1, X_1+D_1, X_1+D_1+D_2,\ldots, X_1+D_1+D_2+\cdots+D_{N-1})\) using a permutation \((D_1, D_3, \dots)\) of \((X_2 - X_1, X_4 - X_3, \dots)\) and a permutation \((D_2, D_4, \dots)\) of \((X_3 - X_2, X_5 - X_4, \dots)\), and all such configurations can be achieved.

Here, the sum of all piece coordinates is:

\[ \begin{aligned} &X_1+(X_1+D_1)+\cdots+(X_1+D_1+D_2+\cdots+D_{N-1}) \\ =&NX_1+(N-1)D_1+(N-2)D_2+\cdots+D_{N-1}\\ =&NX_1+\{ (N-1)D_1+(N-3)D_3+\cdots\}+\{ (N-2)D_2+(N-4)D_4+\cdots\} \end{aligned} \]

This is minimized when \((D_1,D_3,\ldots)\) is \((X_2-X_1, X_4-X_3, \ldots)\) sorted in ascending order, and \((D_2,D_4,\ldots)\) is \((X_3-X_2, X_5-X_4, \ldots)\) sorted in ascending order.
The sum of coordinates in this case can be easily computed by sorting \((X_2-X_1, X_4-X_3, \ldots)\) and \((X_3-X_2, X_5-X_4, \ldots)\) in ascending order, in \(O(N \log N)\) time, which is fast enough.
This solves our problem.

Sample C++ Implementation:

#include <bits/stdc++.h>
using namespace std;


int main() {
	int n;
	long long s,ans;

	cin>>n;
	vector<long long>a(n),d[2];
	for(int i=0;i<n;i++)cin>>a[i];

	for(int i=0;i<n-1;i++)d[i%2].push_back(a[i+1]-a[i]);
	for(int i=0;i<2;i++)sort(d[i].begin(),d[i].end());

	s=a[0],ans=a[0];
	for(int i=0;i<n-1;i++){
		s+=d[i%2][i/2];
		ans+=s;
	}
	cout<<ans<<endl;
	return 0;
}