/* Author : Aaryan Srivastava ^__^ */ 
#include <bits/stdc++.h>
#include <random>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#define pb push_back
#define mp make_pair
#define ff first
#define ss second   
#define rep(i,n) for(int (i) = 0 ; i < (n) ; i++)
#define repA(i,x,y) for(int i = (x) ; i <= (y) ; i++)
#define repD(i,x,y) for(int i = (x) ; i >= (y) ; i--)
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).end()
#define setval(a,val) memset(a,val,sizeof(a))
#define Randomize mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define trav(x , a) for(auto &x : a)
#define sz(a) ((int)a.size())
typedef long long ll ; 

#define int ll

using namespace std;

const int N = 3e5 +5 ;
const int mod = 1e9 + 7 ;
const ll inf = 1e18 ;
const int SZ = 101 ;
const double eps = 1e-9 ;
using namespace __gnu_pbds;
using ordered_set =  tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ;

typedef pair<int, int> pii; 
typedef pair<int , pii> ipii ;
typedef pair<pii , int> piii ; 
typedef unsigned long long ull ;
typedef long double ld;

ll po(ll x,ll y,ll p = mod) {ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}

void solve()
{
    int n ;
    cin >> n;
    int a[n];
    rep(i , n) cin >> a[i];
    // vector<int> v(n); rep(i , n) v[i] = i ;
    // vector<int> bst(n,0);
    // int mx = 0 ;
    // do{
    //     int res = 0 ;
    //     rep(i ,n)
    //         res += abs(i - v[i]) * a[v[i]];
    //     if(res > mx){
    //         rep(i , n) bst[i] = (a[v[i]]);
    //         mx = res ;
    //     }
    // }while(next_permutation(all(v)));
    // rep(i , n) v[i] = i;
    // do{
    //     int res = 0 ;
    //     rep(i ,n)
    //         res += abs(i - v[i]) * a[v[i]];
    //     if(res ==  mx){
    //         static int t = 1 ;
    //         cout << t++ << ": "; 
    //         rep(i , n) cout << (v[i]) << ' ' ;
    //         cout << '\n';
    //         mx = res ;
    //     }
    // }while(next_permutation(all(v)));
    int ans[n] = {};
    map<int , deque<int>> m;
    rep(i , n) m[a[i]].pb(i);
    sort(a , a + n);
    reverse(a , a + n);
    int cur = 0 , ans2 = 0 ,p = 0;
    while(p < n){
        int res1 = 0 , res2 = 0 ;
        res1 = abs(m[a[p]].back()-cur) * a[p] /*, m[a[p++]].pop_back()*/;
        if(p+1 < n){
            // cout << a[p] << ' ' << m[a[p]].front() << '\n';
            res1 += abs(m[a[p+1]].front() - (n-cur-1)) * a[p+1]  /*, m[a[p+1]].pop_front()*/;
        }
        res2 = abs(m[a[p]].front()- (n-cur-1)) * a[p] /*, m[a[p++]].pop_back()*/;
        if(p+1 < n){
            // cout << a[p] << ' ' << m[a[p]].front() << '\n';
            res1 += abs(m[a[p+1]].back() - (cur)) * a[p+1] /* , m[a[p+1]].pop_front()*/;
        }
        if(res1 >= res2){
            res1 = abs(m[a[p]].back()-cur) * a[p] , m[a[p++]].pop_back();
            if(p < n){
                // cout << a[p] << ' ' << m[a[p]].front() << '\n';
                res1 += abs(m[a[p]].front() - (n-cur-1)) * a[p]  , m[a[p++]].pop_front();
            }
            ans2 += res1 ;
        }else{
            res2 = abs(m[a[p]].front()- (n-cur-1)) * a[p] , m[a[p++]].pop_front();
            if(p < n){
                // cout << a[p] << ' ' << m[a[p]].front() << '\n';
                res2 += abs(m[a[p]].back() - (cur)) * a[p]  , m[a[p++]].pop_back();
            }
            ans2 += res2;
        }
        // ans2 += max(res2,res1) ;
        cur++ ;
    }
    // cout << mx << ' ' ;
    cout << ans2 ;
    // rep(i, n) cout << ans[i] << ' ';
    // cout << '\n';
}   

     
int32_t main(int32_t argc, char *argv[])
{
    ios::sync_with_stdio(0);    
    cin.tie(0); cout.tie(0);
    int TC = 1, t = 0;
    //cin >> TC ;
    while(t++ < TC)
    {
        //cout << "Case #" << t << ": " ;
        solve();
        cout << "\n" ;
    }
    return 0;
}