module Main;

// import BinaryHeap;
// import BoolArray;
// import CPLib.Arithmetic;
// import CPLib.Bipartite;
// import CPLib.Bits;
// import CPLib.Convolution;
// import CPLib.DSegtree;
// import CPLib.Graph;
import CPLib.IO;
// import CPLib.LDSegtree;
// import CPLib.LSegtree;
// import CPLib.MaxFlow;
// import CPLib.Memoize;
// import CPLib.MinCostFlow;
// import CPLib.Misc;
// import CPLib.Monoid;
// import CPLib.Segtree;
// import CPLib.String;
// import CPLib.Trait;
// import CPLib.TwoSat;
// import CPLib.UnionFind;
// import CPLib.ZP;
// import HashMap;
// import HashSet;

main : IO () = (
    let iN = *read_i;
    let iAs = *read_is(iN);
    let iAs = iAs.sort;
    let acm = range(0, iN).fold([0], |i, acm| 
        let prev = acm.@(i);
        acm.push_back(iAs.@(i) + prev)
    );
    let ans0 = range(0, iN).map(|i|
        let n = min(i, iN-i-1);
        if n == 0 { 0 };
        let good = |m| (
            let j = iN - m;
            let k = i - m;
            iAs.@(j) + iAs.@(k) - 2 * iAs.@(i) > 0
        );
        let m = (
            if !good(1) {
                0
            };
            if good(n) {
                n
            };
            let lo = 0; let hi = n;
            loop((lo, hi), |(lo, hi)|
                if hi - lo <= 1 {
                    lo.break
                };
                let mid = lo + (hi - lo) / 2;
                if good(mid) {
                    let lo = mid;
                    (lo, hi).continue
                } else {
                    let hi = mid;
                    (lo, hi).continue
                }
            )
        );
        let sum = iAs.@(i) + acm.@(iN) - acm.@(iN - m) + acm.@(i) - acm.@(i-m);
        let score = sum - iAs.@(i) * (1 + 2 * m);
        // eval "score = {}, odd, i = {}, m = {}, sum = {}, iAs.@(i) = {}, medians = {}".debug_eprintfln((score, i, m, sum, iAs.@(i), iAs.@(i) * (1 + 2 * m)));
        score
    ).fold(I64::minimum, max);
    let ans1 = range(0, iN - 1).map(|i|
        let j = i + 1;
        let n = min(iN - j - 1, i);
        if n == 0 { 0 };
        let good = |m| (
            let k = i - m;
            let l = iN - m;
            iAs.@(k) + iAs.@(l) - (iAs.@(i) + iAs.@(j)) > 0
        );
        let m = (
            if !good(1) {
                0
            };
            if good(n) {
                n
            };
            let lo = 0; let hi = n;
            loop((lo, hi), |(lo, hi)|
                if hi - lo <= 1 {
                    lo.break
                };
                let mid = lo + (hi - lo) / 2;
                if good(mid) {
                    let lo = mid;
                    (lo, hi).continue
                } else {
                    let hi = mid;
                    (lo, hi).continue
                }
            )
        );
        let sum2 = iAs.@(i) + iAs.@(j) + acm.@(iN) - acm.@(iN - m) + acm.@(i) - acm.@(i - m);
        let score = sum2 - (iAs.@(i) + iAs.@(j)) * (1 + m);
        // eval "score = {}, even, i = {}, m = {}, sum2 = {}, mediums = {}".debug_eprintfln((score, i, m, sum2, (iAs.@(i) + iAs.@(j)) * (1 + m)));
        score
    ).fold(I64::minimum, max);
    let ans = ans0.max(ans1);
    ans.to_string.println;;
    pure()
);