#pragma target("avx") #include using namespace std; typedef long long ll; typedef long double ld; typedef pair P; typedef vector V; typedef unordered_map U_MAP; typedef priority_queue pq; typedef priority_queue, greater> rpq; const int INF = 1e9, MOD = 1e9 + 7, ohara = 1e6 + 10; const ll LINF = 1e18; #define rep(i, n) for (ll(i) = 0; (i) < (int)(n); (i)++) #define rrep(i, a, b) for (ll i = (a); i < (b); i++) #define rrrep(i, a, b) for (ll i = (a); i >= (b); i--) #define all(v) (v).begin(), (v).end() #define Size(n) (n).size() #define Cout(x) cout << (x) << endl #define doublecout(a) cout << fixed << setprecision(15) << a << endl; #define fi first #define se second #define m_p make_pair #define p_b push_back string to_string(string s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string)s); } string to_string(bool b) { return (b ? "true" : "false"); } template string to_string(pair p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template string to_string(A v) { bool first = true; string res = "{"; for (const auto& x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } void debug_out() { cerr << endl; } template void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) //------ Believe yourself as a genius!!!!!! ------ int dy[] = {1, 0, -1, 0}; int dx[] = {0, 1, 0, -1}; // int dy[]={-1,0,1,-1,1,-1,0,1};int dx[]={-1,-1,-1,0,0,1,1,1}; string alph("abcdefghijklmnopqrstuvwxyz"), s; ll n, cnt, ans, a[ohara], b, c, d, tmp, m, h, w, x, y, sum[ohara], k, q; int main(void) { cin.tie(0); cout.tie(0); ios::sync_with_stdio(false); cin >> n; rep(i, n) cin >> a[i]; sort(a, a + n); rep(i, n) sum[i] = a[i]; rrep(i, 1, n) sum[i] += sum[i - 1]; rrep(i, 1, (n - 1) / 2 + 1) { ll add = sum[i - 1]; add += sum[n - 1] - sum[n - i - 1]; add -= a[i] * i * 2; ans = max(ans, add); } rep(i, n) { a[i] *= 2; } ll tyuu = (a[n / 2] + a[n / 2 - 1]) / 2; rep(i, n) { cnt += a[i] - tyuu; } cnt /= 2; Cout(max(ans, cnt)); return 0; }