#include #include #include #include #include #include #include using namespace std; typedef long long ll; int N; ll a[200000]; ll sum[200001]; ll calc(int l, int r){ return sum[r+1]-sum[l]; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; ll ans = 0; cin >> N; for(int i = 0; i < N; i++){ cin >> a[i]; a[i] *= 2; } sort(a, a+N); for(int i = 0; i < N; i++) sum[i+1] = sum[i]+a[i]; for(int i = 1; i <= N-2; i++){ int n_left = i; int n_right = N-i-1; int l = 1; int r = min(n_left, n_right); ll tmp = 0; if(a[N-1]+a[0]-2*a[i] < 0){ }else if(a[N-r]+a[i-r]-2*a[i] >= 0){ tmp = calc(0, r-1)+calc(N-r, N-1)-2*r*a[i]; }else{ while(r-l > 1){ int c = (l+r)/2; if(a[N-c]+a[c-1]-2*a[i] >= 0) l = c; else r = c; } tmp = calc(i-r, i-1)+calc(N-l, N-1)-2*l*a[i]; } ans = max(ans, tmp); } for(int i = 1; i <= N-3; i++){ int n_left = i; int n_right = N-i-2; int l = 1; int r = min(n_left, n_right); ll m = (a[i]+a[i+1])/2; ll tmp = 0; if(a[N-1]+a[0]-2*m < 0){ }else if(a[N-r]+a[i-r]-2*m >= 0){ tmp = calc(i-r, i-1)+calc(N-r, N-1)-2*r*m; }else{ while(r-l > 1){ int c = (l+r)/2; if(a[N-c]+a[c-1]-2*m >= 0) l = c; else r = c; } tmp = calc(0, l-1)+calc(N-l, N-1)-2*l*m; } ans = max(ans, tmp); } cout << ans/2 << endl; }