#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rrep(i, n) for(int i = n-1; i >= 0; --i)
#define fi first
#define se second
using namespace std;
using lint = long long;
using uint = unsigned int;
using ulint = unsigned long long;
using ldouble = long double;
using pii = pair<int, int>;
using pli = pair<lint, lint>;
using pdd = pair<double, double>;
using pld = pair<ldouble, ldouble>;
using v1i = vector<int>;
using v1li = vector<lint>;
using v2i = vector<vector<int>>;
using v2li = vector<vector<lint>>;
using v3i = vector<vector<vector<int>>>;
using v3li = vector<vector<vector<lint>>>;
using v1b = vector<bool>;
using v2b = vector<vector<bool>>;
using v3b = vector<vector<vector<bool>>>;
using v1c = vector<char>;
using v2c = vector<vector<char>>;
using v3c = vector<vector<vector<char>>>;
constexpr lint mod1 = 1e9+7;
constexpr lint mod2 = 998244353;

int main() {
  int n, l = 0, r, t, k = 1; lint s = 0;
  cin >> n; r = n-1;
  vector<pii> v(n);
  rep(i, n){
    cin >> v[i].fi;
    v[i].se = i;
  }
  sort(v.begin(), v.end());
  reverse(v.begin(), v.end());
  t = v[0].fi;
  queue<int> q;
  rep(i, n-1){
    if(v[i+1].fi == t) ++k;
    else{
      q.push(k);
      t = v[i+1].fi;
      k = 1;
    }
  }
  q.push(t);
  t = 0;
  while(!q.empty()){
    int c = t, d = t+q.top()-1;
    rep(i, q.top()){
      if(i % 2 == 0){
        s += v[c].fi * abs(v[i].se-l);
        ++l;
        ++c;
      }
      else{
        s += v[d].fi * abs(r-v[i].se);
        --r;
        --d;
      }
    t += q.top();
    q.pop();
  }
  cout << s << endl;
  return 0;
}