#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } const long long MAX = 5100000; const long long INF = 1LL << 60; const long long mod = 1000000007LL; //const long long mod = 998244353LL; using namespace std; typedef unsigned long long ull; typedef long long ll; int main() { /* cin.tie(nullptr); ios::sync_with_stdio(false); */ ll N; scanf("%lld", &N); vector a(N); for (ll i = 0; i < N; i++) scanf("%lld", &a[i]); sort(a.begin(), a.end()); vector sum(N + 1); for (ll i = 0; i < N; i++) sum[i + 1] = sum[i] + a[i]; ll res = 0; for (ll i = 0; i < N; i++) { ll l = 0; ll r = min(i + 1, N - i); while (r - l > 1) { ll mid = (l + r) >> 1; ll tmp = -a[i] - a[i]; if (mid > 0) tmp += a[N - mid] + a[i - mid]; if (mid == 0) tmp = INF; if (tmp > 0) l = mid; else r = mid; } chmax(res, sum[N] - sum[N - l] + sum[i] - sum[i - l] - a[i] * 2 * l); //cout << i << " " << l << " " << res << endl; } cout << res << endl; return 0; }