#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 ;
}
I3ByYWdtYSBjb21tZW50KGxpbmtlciwgIi9zdGFjazoyMDAwMDAwMDAiKQovLyNwcmFnbWEgR0NDIG9wdGltaXplKCJPZmFzdCIpCi8vI3ByYWdtYSBHQ0MgdGFyZ2V0KCJzc2Usc3NlMixzc2UzLHNzc2UzLHNzZTQscG9wY250LGFibSxtbXgsYXZ4LHR1bmU9bmF0aXZlIikKI3ByYWdtYSBHQ0Mgb3B0aW1pemUgKCJPMyIpCiNwcmFnbWEgR0NDIHRhcmdldCAoInNzZTQiKQojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KI2luY2x1ZGUgPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+CiNpbmNsdWRlIDxleHQvcGJfZHMvYXNzb2NfY29udGFpbmVyLmhwcD4KIAp1c2luZyBuYW1lc3BhY2Ugc3RkOwp1c2luZyBuYW1lc3BhY2UgX19nbnVfcGJkczsKdHlwZWRlZiB0cmVlPGludCxudWxsX3R5cGUsbGVzczxpbnQ+LHJiX3RyZWVfdGFnLHRyZWVfb3JkZXJfc3RhdGlzdGljc19ub2RlX3VwZGF0ZT4gVHJlZTsKIApjb25zdCBkb3VibGUgUEkgPSA0ICogYXRhbigxKTsKIAojZGVmaW5lIHN6KHgpIChpbnQpKHgpLnNpemUoKQojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIGxkIGxvbmcgZG91YmxlCiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgZWIgZW1wbGFjZV9iYWNrCiNkZWZpbmUgcGlpIHBhaXIgPGludCwgaW50PgojZGVmaW5lIHZpIHZlY3RvcjxpbnQ+CiNkZWZpbmUgZiBmaXJzdAojZGVmaW5lIHMgc2Vjb25kCiNkZWZpbmUgbGIgbG93ZXJfYm91bmQKI2RlZmluZSB1YiB1cHBlcl9ib3VuZAojZGVmaW5lIGFsbCh4KSB4LmJlZ2luKCksIHguZW5kKCkKI2RlZmluZSB2cGkgdmVjdG9yPHBhaXI8aW50LCBpbnQ+PgojZGVmaW5lIHZwZCB2ZWN0b3I8cGFpcjxkb3VibGUsIGRvdWJsZT4+CiNkZWZpbmUgcGQgcGFpcjxkb3VibGUsIGRvdWJsZT4KIAojZGVmaW5lIGYwcihpLGEpIGZvcihpbnQgaT0wO2k8YTtpKyspCiNkZWZpbmUgZjFyKGksYSxiKSBmb3IoaW50IGk9YTtpPGI7aSsrKQogCnZvaWQgZmFzdF9pbygpewogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTsKICAgIGNpbi50aWUoTlVMTCk7CiAgICBjb3V0LnRpZShOVUxMKTsKfQp2b2lkIGlvKHN0cmluZyB0YXNrbmFtZSl7CiAgICBzdHJpbmcgZmluID0gdGFza25hbWUgKyAiLmluIjsKICAgIHN0cmluZyBmb3V0ID0gdGFza25hbWUgKyAiLm91dCI7CiAgICBjb25zdCBjaGFyKiBGSU4gPSBmaW4uY19zdHIoKTsKICAgIGNvbnN0IGNoYXIqIEZPVVQgPSBmb3V0LmNfc3RyKCk7CiAgICBmcmVvcGVuKEZJTiwgInIiLCBzdGRpbik7CiAgICBmcmVvcGVuKEZPVVQsICJ3Iiwgc3Rkb3V0KTsKICAgIGZhc3RfaW8oKTsKfQp2aSBwOwpjb25zdCBpbnQgTUFYID0gMWUzKzU7CnN0cnVjdCBjaGFzaDIgewogICAgaW50IG9wZXJhdG9yKCkocGFpcjxpbnQsIGludD4geCkgY29uc3QgeyByZXR1cm4geC5maXJzdCogMzEgKyB4LnNlY29uZDsgfQp9Owp1bm9yZGVyZWRfbWFwPHBhaXI8aW50LCBpbnQ+LCBpbnQsIGNoYXNoMj4gZHAxOwpncF9oYXNoX3RhYmxlPHBhaXI8aW50LCBpbnQ+LCBpbnQsIGNoYXNoMj4gZHA7CnZwaSBzdGF0ZXNbTUFYXTsKaW50IG47CmNvbnN0IGludCBJTkYgPSAxZTk7CmNvbnN0IGludCBNQVhMID0gMWU2KyA5OwppbnQgbG9jW01BWExdOwppbnQgcHJlW01BWExdOwppbnQgbnVtKGludCBpLCBpbnQgail7CiAgICBpZihpID09IDApewogICAgICAgIHJldHVybiBwcmVbal07CiAgICB9CiAgICBlbHNlewogICAgICAgIHJldHVybiBwcmVbal0gLSBwcmVbaS0xXTsKICAgIH0KfQovL29yaWdpbiBhdCA1MDAwMDAKY29uc3QgaW50IG8gPSA1MDAwMDA7CnZvaWQgY2FsYyhpbnQgeCl7CiAgICBmb3IoYXV0byBpdDogc3RhdGVzW3hdKXsKICAgICAgICBmMHIoaSwgMil7CiAgICAgICAgICAgIGludCBsID0gaXQuZjsKICAgICAgICAgICAgaW50IHIgPSBpdC5zOwogICAgICAgICAgICBpbnQgY3VyOwogICAgICAgICAgICBpZih4ID09IDApewogICAgICAgICAgICAgICAgY3VyID0gbzsKICAgICAgICAgICAgICAgIGRwW21wKGwqMTAsIHIpXSA9IDA7CiAgICAgICAgICAgICAgICBkcFttcChsKjEwKzEsIHIpXSA9IDA7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZXsKICAgICAgICAgICAgICAgIGlmKGkgPT0wKXsKICAgICAgICAgICAgICAgICAgICBjdXIgPSBwW2wrMV07CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlewogICAgICAgICAgICAgICAgICAgIGN1ciA9IHBbci0xXTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgICAgICBmMHIoaiwgMil7CiAgICAgICAgICAgICAgICBpZihqID09IDApewogICAgICAgICAgICAgICAgICAgIGlmKGw+PSAwKXsKICAgICAgICAgICAgICAgICAgICAgICAgaW50IHRpbWUgPSBhYnMocFtsXSAtIGN1cik7CiAgICAgICAgICAgICAgICAgICAgICAgIGludCBhZGQgPSAobi14KSogdGltZTs7CiAgICAgICAgICAgICAgICAgICAgICAgIGRwW21wKChsLTEpKjEwICsgMCwgcildID0gIG1pbihkcFttcCgobC0xKSoxMCArIDAsIHIpXSwgYWRkKyBkcFttcChsKjEwICsgaSwgcildKTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlewogICAgICAgICAgICAgICAgICAgIGlmKHI8PSBuLTEpewogICAgICAgICAgICAgICAgICAgICAgICBpbnQgdGltZSA9IGFicyhwW3JdIC0gY3VyKTsKICAgICAgICAgICAgICAgICAgICAgICAgaW50IGFkZCA9IChuLXgpKiB0aW1lOwogICAgICAgICAgICAgICAgICAgICAgICBkcFttcChsKjEwICsgMSwgIHIrMSldID0gIG1pbihkcFttcChsKjEwICsgMSwgcisxKV0sIGFkZCsgZHBbbXAobCoxMCArIGksIHIpXSk7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQp9CmludCBtYWluKCl7CiAgICBpbygiY293cnVuIik7CiAgICBjaW4gPj4gbjsKICAgIGYwcihpLCBuKXsKICAgICAgICBpbnQgcGk7CiAgICAgICAgY2luID4+IHBpOwogICAgICAgIHBpICs9IDUwMDAwMDsKICAgICAgICBwLmViKHBpKTsKICAgICAgICBsb2NbcGldID0gMTsKICAgIH0KICAgIGYwcihpLCBNQVhMKXsKICAgICAgICBpZihpID09IDApewogICAgICAgICAgICBwcmVbaV0gPSBsb2NbaV07CiAgICAgICAgfQogICAgICAgIGVsc2V7CiAgICAgICAgICAgIHByZVtpXSA9IHByZVtpLTFdICsgbG9jW2ldOwogICAgICAgIH0KICAgIH0KICAgIHNvcnQoYWxsKHApKTsKICAgIGYwcihpLCBuKXsKICAgICAgICBmMHIoaiwgbil7CiAgICAgICAgICAgIGlmKHBbaV0gPG8gJiYgbzwgcFtqXSApewogICAgICAgICAgICAgICAgYXNzZXJ0KG51bShwW2ldLCBwW2pdKSAtIDI+PSAwKTsKICAgICAgICAgICAgICAgIHN0YXRlc1tudW0ocFtpXSwgcFtqXSktMl0uZWIobXAoaSwgaikpOwogICAgICAgICAgICAgICAgZHBbbXAoaSoxMCswLCBqKV0gPSBJTkY7IC8vIGxlZnQKICAgICAgICAgICAgICAgIGRwW21wKGkqMTArMSwgaildID0gSU5GOyAvLyByaWdodAogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgLy9yZXR1cm4gMDsKICAgIGYxcihpLCAtMSwgbisxKXsKICAgICAgICBkcFttcCgtMSoxMCwgaSldID0gSU5GOwogICAgICAgIGRwW21wKC0xKjEwKzEsIGkpXSA9IElORjsKICAgICAgICBkcFttcChpKjEwLCBuKV0gPSBJTkY7CiAgICAgICAgZHBbbXAoaSoxMCArIDEsIG4pXSA9IElORjsKICAgIH0KICAgIGYwcihpLCBuKXsKICAgICAgICBpZihwW2ldIDwgbyl7CiAKICAgICAgICAgICAgc3RhdGVzW251bShwW2ldLCBNQVhMLTEpLTFdLmViKG1wKGksIG4pKTsKICAgICAgICB9CiAgICAgICAgZWxzZXsKICAgICAgICAgICAgc3RhdGVzW251bSgwLCBwW2ldKS0xXS5lYihtcCgtMSwgaSkpOwogICAgICAgIH0KICAgIH0KICAgIGYwcihpLCBuKzEpewogICAgICAgIGNhbGMoaSk7CiAgICB9CiAgICBjb3V0IDw8IG1pbihkcFttcCgtMSoxMCArIDEsIG4pXSwgZHBbbXAoLTEqMTAsIG4pXSApPDwgZW5kbDsKICAgIC8vY291dCA8PCBkcFttcCgxKjEwKzEsIDQpXSA8PCBlbmRsOwogICAgcmV0dXJuIDA7Cn0KIA==