#include <bits/stdc++.h>
using namespace std;

int n;
long long a[100005];  // độ cách nhiệt của các khối hình vuông

// Tổng a không phụ thuộc cách xếp, nên chỉ cần tối đa hóa phần cộng thêm: tổng max(0, a[i+1]-a[i]).

// Sub 1: vét cạn — thử mọi cách xếp (hoán vị) và lấy cách có tổng cộng thêm lớn nhất. Dùng khi n <= 8.
void sub1() {
    vector<long long> v(a + 1, a + n + 1);
    sort(v.begin(), v.end());
    long long sum = 0, best = 0;
    for (long long x : v) sum += x;
    do {
        long long extra = 0;
        for (int i = 0; i + 1 < n; i++)
            extra += max(0LL, v[i + 1] - v[i]);
        best = max(best, extra);
    } while (next_permutation(v.begin(), v.end()));
    cout << sum + best << "\n";
}

// Sub 2: công thức. Chia dãy thành các nhóm, mỗi nhóm xếp tăng dần thì được cộng (max - min) của nhóm.
// Tốt nhất là ghép b[i] (nhỏ) với b[n-1-i] (lớn) cho i = 0..n/2-1, phần còn lại (nếu có) đứng riêng. O(n log n).
void sub2() {
    vector<long long> b(a + 1, a + n + 1);
    sort(b.begin(), b.end());
    long long ans = 0;
    for (long long x : b) ans += x;
    for (int i = 0; i < n / 2; i++)
        ans += b[n - 1 - i] - b[i];
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (n <= 8) sub1();  // dữ liệu nhỏ: thử mọi cách xếp
    else sub2();         // công thức
    return 0;
}