ある時点において、座標が小さい方から \(i\) 番目 \((1\leq i\leq N)\) のコマの座標を \(x_i\) 、座標が小さい方から \(j\) 番目 \((1\leq j\leq N-1)\) のコマと \(j+1\) 番目のコマの間の距離（座標の差）を \(d_j\) とします。
この状態から、\(i_0\) \((1\leq i_0\leq N-3)\)を選択して操作を行ったときに起きる変化について考えます。
動くのは操作前の時点で、座標が小さい方から \(i_0+1\) 番目のコマと \(i_0+2\) 番目のコマだけですが、これらのコマは次のように動きます。

• 座標が小さい方から \(i_0+1\) 番目のコマは \(x_{i_0+1}\) から、\(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}\) へ移る。
• 座標が小さい方から \(i_0+2\) 番目のコマは \(x_{i_0+2}\) から、\(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}\) へ移る。

\(x_{i_0}<x_{i_0+1}<x_{i_0+2}<x_{i_0+3}\) より、\(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}\) であり、コマの順番としては \(i_0+1\) 番目のコマと \(i_0+2\) 番目のコマだけが入れ替わり、それ以外は変化しません。
操作後における座標が小さい方から \(j\) 番目 \((1\leq j\leq N-1)\) のコマと \(j+1\) 番目のコマの間の距離を \(d'_j\) とすると、\(j\neq i_0,i_0+1,i_0+2\) については \(d'_j=d_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}\)

よって、この操作は \(d_{i_0}\) と \(d_{i_0+2}\) を入れ替える操作に対応しています。
ゆえに、 \((d_1,d_3,\ldots)\) はつねに \((X_2-X_1, X_4-X_3, \ldots)\) の並び替えであり、 \((d_2,d_4,\ldots)\) は \((X_3-X_2, X_5-X_4, \ldots)\) の並び替えとなります。
逆に、 \((d_1,d_3,\ldots)\) に対する操作と \((d_2,d_4,\ldots)\) に対する操作はそれぞれ独立に行うことができ、またそれぞれの列について隣接互換を繰り返すことで任意の並び替えを達成できます。
また、最も左のコマの座標は操作によって変化することがないため \(x_1=X_1\) です。
これらより、操作を繰り返した後の配置のコマの座標を小さい方から順に並べた列としてあり得るものは、\((X_2-X_1, X_4-X_3, \ldots)\) の並び替え \((D_1,D_3,\ldots)\) と \((X_3-X_2, X_5-X_4, \ldots)\) の並び替え \((D_2,D_4,\ldots)\) を用いて、\((X_1, X_1+D_1, X_1+D_1+D_2,\ldots, X_1+D_1+D_2+\cdots+D_{N-1})\) と記述できるようなものに限られ、かつこのようなものはすべて達成することができます。

このときすべてのコマの座標の総和は、

\[ \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} \]

と書くことができますが、これが最小となるのは \((D_1,D_3,\ldots)\) が \((X_2-X_1, X_4-X_3, \ldots)\) を昇順に並べ替えたものであり、\((D_2,D_4,\ldots)\) が \((X_3-X_2, X_5-X_4, \ldots)\) を昇順に並べ替えたものであるときとなります。
このときの座標の総和は \((X_2-X_1, X_4-X_3, \ldots)\) および \((X_3-X_2, X_5-X_4, \ldots)\) をそれぞれ昇順にソートすることで容易に計算することができ、時間計算量も\(O(N\log N)\) であるため十分高速です。
よって、この問題を解くことができました。

c++ による実装例:

#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;
}