#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> dp;
gp_hash_table< pair< int , int > , int , chash2> dp1;
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 ;
}
I3ByYWdtYSBjb21tZW50KGxpbmtlciwgIi9zdGFjazoyMDAwMDAwMDAiKQovLyNwcmFnbWEgR0NDIG9wdGltaXplKCJPZmFzdCIpCi8vI3ByYWdtYSBHQ0MgdGFyZ2V0KCJzc2Usc3NlMixzc2UzLHNzc2UzLHNzZTQscG9wY250LGFibSxtbXgsYXZ4LHR1bmU9bmF0aXZlIikKI3ByYWdtYSBHQ0Mgb3B0aW1pemUgKCJPMyIpCiNwcmFnbWEgR0NDIHRhcmdldCAoInNzZTQiKQojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KI2luY2x1ZGUgPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+CiNpbmNsdWRlIDxleHQvcGJfZHMvYXNzb2NfY29udGFpbmVyLmhwcD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnVzaW5nIG5hbWVzcGFjZSBfX2dudV9wYmRzOwp0eXBlZGVmIHRyZWU8aW50LG51bGxfdHlwZSxsZXNzPGludD4scmJfdHJlZV90YWcsdHJlZV9vcmRlcl9zdGF0aXN0aWNzX25vZGVfdXBkYXRlPiBUcmVlOwoKY29uc3QgZG91YmxlIFBJID0gNCAqIGF0YW4oMSk7CgojZGVmaW5lIHN6KHgpIChpbnQpKHgpLnNpemUoKQojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIGxkIGxvbmcgZG91YmxlCiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgZWIgZW1wbGFjZV9iYWNrCiNkZWZpbmUgcGlpIHBhaXIgPGludCwgaW50PgojZGVmaW5lIHZpIHZlY3RvcjxpbnQ+CiNkZWZpbmUgZiBmaXJzdAojZGVmaW5lIHMgc2Vjb25kCiNkZWZpbmUgbGIgbG93ZXJfYm91bmQKI2RlZmluZSB1YiB1cHBlcl9ib3VuZAojZGVmaW5lIGFsbCh4KSB4LmJlZ2luKCksIHguZW5kKCkKI2RlZmluZSB2cGkgdmVjdG9yPHBhaXI8aW50LCBpbnQ+PgojZGVmaW5lIHZwZCB2ZWN0b3I8cGFpcjxkb3VibGUsIGRvdWJsZT4+CiNkZWZpbmUgcGQgcGFpcjxkb3VibGUsIGRvdWJsZT4KCiNkZWZpbmUgZjByKGksYSkgZm9yKGludCBpPTA7aTxhO2krKykKI2RlZmluZSBmMXIoaSxhLGIpIGZvcihpbnQgaT1hO2k8YjtpKyspCgp2b2lkIGZhc3RfaW8oKXsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAgICBjaW4udGllKE5VTEwpOwogICAgY291dC50aWUoTlVMTCk7Cn0Kdm9pZCBpbyhzdHJpbmcgdGFza25hbWUpewogICAgc3RyaW5nIGZpbiA9IHRhc2tuYW1lICsgIi5pbiI7CiAgICBzdHJpbmcgZm91dCA9IHRhc2tuYW1lICsgIi5vdXQiOwogICAgY29uc3QgY2hhciogRklOID0gZmluLmNfc3RyKCk7CiAgICBjb25zdCBjaGFyKiBGT1VUID0gZm91dC5jX3N0cigpOwogICAgZnJlb3BlbihGSU4sICJyIiwgc3RkaW4pOwogICAgZnJlb3BlbihGT1VULCAidyIsIHN0ZG91dCk7CiAgICBmYXN0X2lvKCk7Cn0KdmkgcDsKY29uc3QgaW50IE1BWCA9IDFlMys1OwpzdHJ1Y3QgY2hhc2gyIHsKICAgIGludCBvcGVyYXRvcigpKHBhaXI8aW50LCBpbnQ+IHgpIGNvbnN0IHsgcmV0dXJuIHguZmlyc3QqIDMxICsgeC5zZWNvbmQ7IH0KfTsKdW5vcmRlcmVkX21hcDxwYWlyPGludCwgaW50PiwgaW50LCBjaGFzaDI+IGRwOwpncF9oYXNoX3RhYmxlPHBhaXI8aW50LCBpbnQ+LCBpbnQsIGNoYXNoMj4gZHAxOwp2cGkgc3RhdGVzW01BWF07CmludCBuOwpjb25zdCBpbnQgSU5GID0gMWU5Owpjb25zdCBpbnQgTUFYTCA9IDFlNisgOTsKaW50IGxvY1tNQVhMXTsKaW50IHByZVtNQVhMXTsKaW50IG51bShpbnQgaSwgaW50IGopewogICAgaWYoaSA9PSAwKXsKICAgICAgICByZXR1cm4gcHJlW2pdOwogICAgfQogICAgZWxzZXsKICAgICAgICByZXR1cm4gcHJlW2pdIC0gcHJlW2ktMV07CiAgICB9Cn0KLy9vcmlnaW4gYXQgNTAwMDAwCmNvbnN0IGludCBvID0gNTAwMDAwOwp2b2lkIGNhbGMoaW50IHgpewogICAgZm9yKGF1dG8gaXQ6IHN0YXRlc1t4XSl7CiAgICAgICAgZjByKGksIDIpewogICAgICAgICAgICBpbnQgbCA9IGl0LmY7CiAgICAgICAgICAgIGludCByID0gaXQuczsKICAgICAgICAgICAgaW50IGN1cjsKICAgICAgICAgICAgaWYoeCA9PSAwKXsKICAgICAgICAgICAgICAgIGN1ciA9IG87CiAgICAgICAgICAgICAgICBkcFttcChsKjEwLCByKV0gPSAwOwogICAgICAgICAgICAgICAgZHBbbXAobCoxMCsxLCByKV0gPSAwOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2V7CiAgICAgICAgICAgICAgICBpZihpID09MCl7CiAgICAgICAgICAgICAgICAgICAgY3VyID0gcFtsKzFdOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZXsKICAgICAgICAgICAgICAgICAgICBjdXIgPSBwW3ItMV07CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZjByKGosIDIpewogICAgICAgICAgICAgICAgaWYoaiA9PSAwKXsKICAgICAgICAgICAgICAgICAgICBpZihsPj0gMCl7CiAgICAgICAgICAgICAgICAgICAgICAgIGludCB0aW1lID0gYWJzKHBbbF0gLSBjdXIpOwogICAgICAgICAgICAgICAgICAgICAgICBpbnQgYWRkID0gKG4teCkqIHRpbWU7OwogICAgICAgICAgICAgICAgICAgICAgICBkcFttcCgobC0xKSoxMCArIDAsIHIpXSA9ICBtaW4oZHBbbXAoKGwtMSkqMTAgKyAwLCByKV0sIGFkZCsgZHBbbXAobCoxMCArIGksIHIpXSk7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgZWxzZXsKICAgICAgICAgICAgICAgICAgICBpZihyPD0gbi0xKXsKICAgICAgICAgICAgICAgICAgICAgICAgaW50IHRpbWUgPSBhYnMocFtyXSAtIGN1cik7CiAgICAgICAgICAgICAgICAgICAgICAgIGludCBhZGQgPSAobi14KSogdGltZTsKICAgICAgICAgICAgICAgICAgICAgICAgZHBbbXAobCoxMCArIDEsICByKzEpXSA9ICBtaW4oZHBbbXAobCoxMCArIDEsIHIrMSldLCBhZGQrIGRwW21wKGwqMTAgKyBpLCByKV0pOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KfQppbnQgbWFpbigpewogICAgaW8oImNvd3J1biIpOwogICAgY2luID4+IG47CiAgICBmMHIoaSwgbil7CiAgICAgICAgaW50IHBpOwogICAgICAgIGNpbiA+PiBwaTsKICAgICAgICBwaSArPSA1MDAwMDA7CiAgICAgICAgcC5lYihwaSk7CiAgICAgICAgbG9jW3BpXSA9IDE7CiAgICB9CiAgICBmMHIoaSwgTUFYTCl7CiAgICAgICAgaWYoaSA9PSAwKXsKICAgICAgICAgICAgcHJlW2ldID0gbG9jW2ldOwogICAgICAgIH0KICAgICAgICBlbHNlewogICAgICAgICAgICBwcmVbaV0gPSBwcmVbaS0xXSArIGxvY1tpXTsKICAgICAgICB9CiAgICB9CiAgICBzb3J0KGFsbChwKSk7CiAgICBmMHIoaSwgbil7CiAgICAgICAgZjByKGosIG4pewogICAgICAgICAgICBpZihwW2ldIDxvICYmIG88IHBbal0gKXsKICAgICAgICAgICAgICAgIGFzc2VydChudW0ocFtpXSwgcFtqXSkgLSAyPj0gMCk7CiAgICAgICAgICAgICAgICBzdGF0ZXNbbnVtKHBbaV0sIHBbal0pLTJdLmViKG1wKGksIGopKTsKICAgICAgICAgICAgICAgIGRwW21wKGkqMTArMCwgaildID0gSU5GOyAvLyBsZWZ0CiAgICAgICAgICAgICAgICBkcFttcChpKjEwKzEsIGopXSA9IElORjsgLy8gcmlnaHQKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIC8vcmV0dXJuIDA7CiAgICBmMXIoaSwgLTEsIG4rMSl7CiAgICAgICAgZHBbbXAoLTEqMTAsIGkpXSA9IElORjsKICAgICAgICBkcFttcCgtMSoxMCsxLCBpKV0gPSBJTkY7CiAgICAgICAgZHBbbXAoaSoxMCwgbildID0gSU5GOwogICAgICAgIGRwW21wKGkqMTAgKyAxLCBuKV0gPSBJTkY7CiAgICB9CiAgICBmMHIoaSwgbil7CiAgICAgICAgaWYocFtpXSA8IG8pewoKICAgICAgICAgICAgc3RhdGVzW251bShwW2ldLCBNQVhMLTEpLTFdLmViKG1wKGksIG4pKTsKICAgICAgICB9CiAgICAgICAgZWxzZXsKICAgICAgICAgICAgc3RhdGVzW251bSgwLCBwW2ldKS0xXS5lYihtcCgtMSwgaSkpOwogICAgICAgIH0KICAgIH0KICAgIGYwcihpLCBuKzEpewogICAgICAgIGNhbGMoaSk7CiAgICB9CiAgICBjb3V0IDw8IG1pbihkcFttcCgtMSoxMCArIDEsIG4pXSwgZHBbbXAoLTEqMTAsIG4pXSApPDwgZW5kbDsKICAgIC8vY291dCA8PCBkcFttcCgxKjEwKzEsIDQpXSA8PCBlbmRsOwogICAgcmV0dXJuIDA7Cn0K