#include<bits/stdc++.h> using namespace std; using Int = long long; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} //INSERT ABOVE HERE signed main(){ Int n; cin>>n; vector<Int> as(n); for(Int i=0;i<n;i++) cin>>as[i]; sort(as.begin(),as.end()); vector<Int> sm(n+1,0); for(Int i=0;i<n;i++) sm[i+1]=sm[i]+as[i]; Int ans=0; // odd for(Int c=0;c<n;c++){ Int l=0,r=min(c+1,n-c); while(l+1<r){ Int m=(l+r)>>1; if(as[c]+as[c]<=as[c-m]+as[n-m]) l=m; else r=m; } // [c-l, c], [n-l, n) Int cnt=l*2+1; chmax(ans,sm[c+1]-sm[c-l]+sm[n]-sm[n-l]-as[c]*cnt); } // cout<<ans<<endl; // even for(Int c=0;c+1<n;c++){ Int l=0,r=min(c+1,n-(c+1)); while(l+1<r){ Int m=(l+r)>>1; if(as[c]+as[c+1]<=as[c-m]+as[n-m]) l=m; else r=m; } // [c-l, c+1], [n-l, n) Int cnt=l*2+2; chmax(ans,sm[c+2]-sm[c-l]+sm[n]-sm[n-l]-(as[c]+as[c+1])*cnt/2); } cout<<ans<<endl; return 0; }