#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> Tree;

const double PI = 4 * atan(1);

#define sz(x) (int)(x).size()
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair<int, int>
#define vi vector<int>
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define vpi vector<pair<int, int>>
#define vpd vector<pair<double, double>>
#define pd pair<double, double>

#define f0r(i, a) for (int i = 0; i < a; i++)
#define f1r(i, a, b) for (int i = a; i < b; i++)

void fast_io() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
void io(string taskname) {
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char *FIN = fin.c_str();
    const char *FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
    fast_io();
}
vi p;
const int MAX = 1e3 + 5;
unsigned hash_f(unsigned x) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    return x;
}

struct chash2 {
    int operator()(pair<int, int> x) const { return hash_f(x.first) * 31 + hash_f(x.second); }
};

unordered_map<pair<int, int>, int, chash2> dp1;
gp_hash_table<pair<int, int>, int, chash2> dp;
vpi states[MAX];
int n;
const int INF = 1e9;
const int MAXL = 1e6 + 9;
int loc[MAXL];
int pre[MAXL];
int num(int i, int j) {
    if (i == 0) {
        return pre[j];
    } else {
        return pre[j] - pre[i - 1];
    }
}
// origin at 500000
const int o = 500000;
void calc(int x) {
    for (auto it : states[x]) {
        f0r(i, 2) {
            int l = it.f;
            int r = it.s;
            int cur;
            if (x == 0) {
                cur = o;
                dp[mp(l * 10, r)] = 0;
                dp[mp(l * 10 + 1, r)] = 0;
            } else {
                if (i == 0) {
                    cur = p[l + 1];
                } else {
                    cur = p[r - 1];
                }
            }
            f0r(j, 2) {
                if (j == 0) {
                    if (l >= 0) {
                        int time = abs(p[l] - cur);
                        int add = (n - x) * time;
                        ;
                        dp[mp((l - 1) * 10 + 0, r)] = min(dp[mp((l - 1) * 10 + 0, r)], add + dp[mp(l * 10 + i, r)]);
                    }
                } else {
                    if (r <= n - 1) {
                        int time = abs(p[r] - cur);
                        int add = (n - x) * time;
                        dp[mp(l * 10 + 1, r + 1)] = min(dp[mp(l * 10 + 1, r + 1)], add + dp[mp(l * 10 + i, r)]);
                    }
                }
            }
        }
    }
}
int main() {
    // io("cowrun");
    cin >> n;
    f0r(i, n) {
        int pi;
        cin >> pi;
        pi += 500000;
        p.eb(pi);
        loc[pi] = 1;
    }
    f0r(i, MAXL) {
        if (i == 0) {
            pre[i] = loc[i];
        } else {
            pre[i] = pre[i - 1] + loc[i];
        }
    }
    sort(all(p));
    f0r(i, n) {
        f0r(j, n) {
            if (p[i] < o && o < p[j]) {
                assert(num(p[i], p[j]) - 2 >= 0);
                states[num(p[i], p[j]) - 2].eb(mp(i, j));
                dp[mp(i * 10 + 0, j)] = INF; // left
                dp[mp(i * 10 + 1, j)] = INF; // right
            }
        }
    }
    // return 0;
    f1r(i, -1, n + 1) {
        dp[mp(-1 * 10, i)] = INF;
        dp[mp(-1 * 10 + 1, i)] = INF;
        dp[mp(i * 10, n)] = INF;
        dp[mp(i * 10 + 1, n)] = INF;
    }
    f0r(i, n) {
        if (p[i] < o) {

            states[num(p[i], MAXL - 1) - 1].eb(mp(i, n));
        } else {
            states[num(0, p[i]) - 1].eb(mp(-1, i));
        }
    }
    f0r(i, n + 1) { calc(i); }
    cout << min(dp[mp(-1 * 10 + 1, n)], dp[mp(-1 * 10, n)]) << endl;
    // cout << dp[mp(1*10+1, 4)] << endl;
    return 0;
}