#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 int inf = 1 << 28; 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 (int i = 0; i < N; i++) scanf("%lld", &a[i]); sort(a.begin(), a.end()); vector sum(N + 1); for (int i = 0; i < N; i++) sum[i + 1] = sum[i] + a[i]; ll res = 0; for (ll i = 0; i < N; i++) { ll left = 0; ll right = min(i, N - i - 1) + 1; while (right - left > 1) { ll mid = (left + right) >> 1; if (a[N - 1 - mid] + a[i - mid] >= a[i] * 2) left = mid; else right = mid; } ll tmp = sum[N] - sum[N - left] + sum[i] - sum[i - left] - a[i] * 2 * left; chmax(res, tmp); } cout << res << endl; /* おまじないを使ったらscanfとprintf関連注意!!!!!!!!!!!! */ }