#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;
struct chash2 {
    int operator()(pair<int, int> x) const { return x.first* 31 + 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;
}