#include<iostream>
#include<algorithm>
using namespace std;
int N;
long A[2<<17];
long S[2<<17];
main()
{
	cin>>N;
	for(int i=0;i<N;i++)cin>>A[i];
	sort(A,A+N);
	for(int i=0;i<N;i++)S[i+1]=S[i]+A[i];
	long ans=0;
	for(int i=1;i<N-1;i++)
	{
		int lim=min(i,N-1-i);
		long L=0,R=lim+1;
		while(R-L>1)
		{
			long M=(L+R)/2;
			if(A[N-M]+A[i-M]>A[i]*2)L=M;
			else R=M;
		}
		ans=max(ans,S[N]-S[N-L]+S[L]-2*L*A[i]);
	}
	cout<<ans<<endl;
}