//https://atcoder.jp/contests/abc163/tasks/abc163_b

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <limits>
#include <stack>
#include <math.h>
#include <cstdint>
#include <numeric>
#include <random>
#include <chrono>
#include <deque>
#define REP(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define RREP(i,n) for(ll i=(n)-1; i>=0; --i)
#define SREP(i,s,n) for(ll i=(s), i##_len=(n); i<i##_len; ++i)
#define ALL(v) (v).begin(),(v).end()

using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

template <typename T>
T gcd(T a, T b) {
    if(a < b) gcd(b, a);
    if (b == 1) return 1;
    T r;
    while ((r=a%b)) {
        a = b;
        b = r;
    }
    return b;
}

template<typename T>
struct UnionFind {
    vector<T> par;
    vector<T> rank;
    
    UnionFind(T n = 1) {
        init(n);
    }
    
    void init(T n = 1) {
        par.resize(n); rank.resize(n);
        for (T i = 0; i < n; ++i) {
            par[i] = i;
            rank[i] = 0;
        }
    }
    
    int root(T x) {
        if (par[x] == x) {
            return x;
        }
        else {
            int r = root(par[x]);
            return par[x] = r;
        }
    }
    
    bool issame(T x, T y) {
        return root(x) == root(y);
    }
    
    bool merge(T x, T y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        return true;
    }
};


//#define INF (ll(1e18))

template< typename Monoid, typename OperatorMonoid = Monoid >
struct LazySegmentTree {
  using F = function< Monoid(Monoid, Monoid) >;
  using G = function< Monoid(Monoid, OperatorMonoid) >;
  using H = function< OperatorMonoid(OperatorMonoid, OperatorMonoid) >;

  ll sz, height;
  vector< Monoid > data;
  vector< OperatorMonoid > lazy;
  const F f;
  const G g;
  const H h;
  const Monoid M1;
  const OperatorMonoid OM0;


  LazySegmentTree(ll n, const F f, const G g, const H h,
                  const Monoid &M1, const OperatorMonoid OM0)
      : f(f), g(g), h(h), M1(M1), OM0(OM0) {
    sz = 1;
    height = 0;
    while(sz < n) sz <<= 1, height++;
    data.assign(2 * sz, M1);
    lazy.assign(2 * sz, OM0);
  }

  void set(ll k, const Monoid &x) {
    data[k + sz] = x;
  }

  void build() {
    for(int k = sz - 1; k > 0; k--) {
      data[k] = f(data[2 * k + 0], data[2 * k + 1]);
    }
  }

  inline void propagate(ll k) {
    if(lazy[k] != OM0) {
      lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);
      lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
      data[k] = reflect(k);
      lazy[k] = OM0;
    }
  }

  inline Monoid reflect(ll k) {
    return lazy[k] == OM0 ? data[k] : g(data[k], lazy[k]);
  }

  inline void recalc(ll k) {
    while(k >>= 1) data[k] = f(reflect(2 * k + 0), reflect(2 * k + 1));
  }

  inline void thrust(ll k) {
    for(int i = height; i > 0; i--) propagate(k >> i);
  }

  void update(ll a, ll b, const OperatorMonoid &x) {
    thrust(a += sz);
    thrust(b += sz - 1);
    for(int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
      if(l & 1) lazy[l] = h(lazy[l], x), ++l;
      if(r & 1) --r, lazy[r] = h(lazy[r], x);
    }
    recalc(a);
    recalc(b);
  }

  Monoid query(ll a, ll b) {
    thrust(a += sz);
    thrust(b += sz - 1);
    Monoid L = M1, R = M1;
    for(int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
      if(l & 1) L = f(L, reflect(l++));
      if(r & 1) R = f(reflect(--r), R);
    }
    return f(L, R);
  }

  Monoid operator[](const int &k) {
    return query(k, k + 1);
  }

  template< typename C >
  int find_subtree(ll a, const C &check, Monoid &M, bool type) {
    while(a < sz) {
      propagate(a);
      Monoid nxt = type ? f(reflect(2 * a + type), M) : f(M, reflect(2 * a + type));
      if(check(nxt)) a = 2 * a + type;
      else M = nxt, a = 2 * a + 1 - type;
    }
    return a - sz;
  }

  template< typename C >
  int find_first(ll a, const C &check) {
    Monoid L = M1;
    if(a <= 0) {
      if(check(f(L, reflect(1)))) return find_subtree(1, check, L, false);
      return -1;
    }
    thrust(a + sz);
    int b = sz;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) {
        Monoid nxt = f(L, reflect(a));
        if(check(nxt)) return find_subtree(a, check, L, false);
        L = nxt;
        ++a;
      }
    }
    return -1;
  }


  template< typename C >
  int find_last(ll b, const C &check) {
    Monoid R = M1;
    if(b >= sz) {
      if(check(f(reflect(1), R))) return find_subtree(1, check, R, true);
      return -1;
    }
    thrust(b + sz - 1);
    int a = sz;
    for(b += sz; a < b; a >>= 1, b >>= 1) {
      if(b & 1) {
        Monoid nxt = f(reflect(--b), R);
        if(check(nxt)) return find_subtree(b, check, R, true);
        R = nxt;
      }
    }
    return -1;
  }
};


int msb(ll x) {
    int n = 0;
    while (x > 0) {
        x/=2;
        n++;
    }
    return n;
}


template <ll Modulus> class modint {
public:
    ll a;

    constexpr modint(const ll x = 0) noexcept : a(x % Modulus) {}
    constexpr ll &value() noexcept { return a; }
    constexpr operator int() const { return a; }
    constexpr operator long long() const { return a; }
    constexpr const ll &value() const noexcept { return a; }
    constexpr modint operator+(const modint rhs) const noexcept {
        return modint(*this) += rhs;
    }
    constexpr modint operator+(const ll rhs) const noexcept {
        return modint(*this) += rhs;
    }
    constexpr modint operator-(const modint rhs) const noexcept {
        return modint(*this) -= rhs;
    }
    constexpr modint operator-(const ll rhs) const noexcept {
        return modint(*this) -= rhs;
    }
    constexpr modint operator*(const modint rhs) const noexcept {
        return modint(*this) *= rhs;
    }
    constexpr modint operator*(const ll rhs) const noexcept {
        return modint(*this) *= rhs;
    }
    constexpr modint operator/(const modint rhs) const noexcept {
        return modint(*this) /= rhs;
    }
    constexpr modint operator/(const ll rhs) const noexcept {
        return modint(*this) /= rhs;
    }
    constexpr modint &operator+=(const modint rhs) noexcept {
        a += rhs.a;
        if (a >= Modulus) {
            a -= Modulus;
        }
        return *this;
    }
    constexpr modint &operator-=(const modint rhs) noexcept {
        if (a < rhs.a) {
            a += Modulus;
        }
        a -= rhs.a;
        return *this;
    }
    constexpr modint &operator*=(const modint rhs) noexcept {
        a = a * rhs.a % Modulus;
        return *this;
    }
    constexpr modint &operator/=(modint rhs) noexcept {
        ll exp = Modulus - 2;
        while (exp) {
            if (exp % 2) {
                *this *= rhs;
            }
            rhs *= rhs;
            exp /= 2;
        }
        return *this;
    }
};

#define MOD (ll(1e9+7))

using Weight = int;
using Capacity = int;
struct Edge {
    int src, dst;
    Weight weight;
    Edge() : src(0), dst(0), weight(0) {}
    Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) {}
};
using Edges = std::vector<Edge>;
using Graph = std::vector<Edges>;

Edge double_sweep(const Graph &g, int s = 0) {
    static const Weight INF = std::numeric_limits<Weight>::max() / 8;
    static const auto bfs = [](const Graph &g, int s, std::queue<int> &q, std::vector<int> &dist) {
        while (q.size()) q.pop();
        q.push(s);
        int n = g.size();
        dist.assign(n, INF);
        dist[s] = 0;
        while (q.size()) {
            int u = q.front();
            q.pop();
            for (auto &e : g[u]) {
                int v = e.dst;
                if (dist[v] == INF) {
                    dist[v] = dist[u] + e.weight;
                    q.push(v);
                }
            }
        }
        return dist;
    };
    std::vector<Weight> dist;
    std::queue<int> q;
    bfs(g, s, q, dist);
    int n = g.size(), u = -1, v = -1;
    for (int i = 0; i < n; i++)
        if (dist[i] != INF && (u == -1 || dist[i] > dist[u])) u = i;
    bfs(g, u, q, dist);
    for (int i = 0; i < n; i++)
        if (dist[i] != INF && (v == -1 || dist[i] > dist[v])) v = i;
    Weight d = dist[v];
    if (u > v) std::swap(u, v);
    return Edge(u, v, d);
}


void add_edge(Graph &g, int a, int b, Weight w = 1) {
    g[a].emplace_back(a, b, w);
    g[b].emplace_back(b, a, w);
}

int f(vector<ll> &l, ll b, ll N) {
    vector<ll> mi(3);
    vector<ll> ret(N);
    REP(i, N) {
        if (l[i]%2) {
            if (mi[1]*3+1 <= N) {
                ret[i] = mi[1]*3+1;
                mi[1]++;
            } else if (mi[0]*3+3 <= N) {
                ret[i] = mi[0]*3+3;
                mi[0]++;
            } else {
                return 0;
            }
        }
        else{
            if (mi[2]*3+2 <= N) {
                ret[i] = mi[2]*3+2;
                mi[2]++;
            } else if (mi[0]*3+3 <= N) {
                ret[i] = mi[0]*3+3;
                mi[0]++;
            } else {
                return 0;
            }
        }
    }
    
    REP(i, N) {
        cout << ret[i] << " ";
    }
    cout << endl;
    return 1;
}


bool comp(pair<ll, ll> a, pair<ll, ll> b) {
    if (a.first == b.first) {
        return a.second > b.second;
    }
    return a.first > b.first;
}


int main(int argc, const char * argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    vector<pair<ll, ll>> A(N);
    REP(i, N) {
        cin >> A[i].first;
        A[i].second = i;
    }
    vector<pair<ll, ll>> front, back;
    sort(ALL(A), comp);
    REP(i, N) {
        ll j = i;
        vector<ll> indice;
        for(;j<N && A[i].first == A[j].first;j++) {
            indice.push_back(A[j].second);
        }
        sort(ALL(indice));
        
        ll activeness = A[i].first;
        
        ll l = 0, r = indice.size()-1;
        while (l <= r) {
            ll fi = front.size();
            ll bi = N-1-back.size();
            
            ll sf = abs(fi-indice[l]);
            ll sb = abs(bi-indice[l]);
            ll bf = abs(fi-indice[r]);
            ll bb = abs(bi-indice[r]);
            ll ma = max(sf, max(sb, max(bf, bb)));
            if (ma == sf) {
                front.push_back(make_pair(activeness, indice[l]));
                l++;
            } else if (ma == sb) {
                back.push_back(make_pair(activeness, indice[l]));
                l++;
            } else if (ma == bf) {
                front.push_back(make_pair(activeness, indice[r]));
                r--;
            } else {
                back.push_back(make_pair(activeness, indice[r]));
                r--;
            }
            
        }
        i = j-1;
    }
    ll score = 0;
    
    REP(i, back.size()) {
        front.push_back(back[back.size()-1-i]);
    }
    
    REP(i, front.size()) {
        ll j = i;
        
        vector<ll> indice;
        for(;j<N && front[i].first == front[j].first;j++) {
            indice.push_back(front[j].second);
        }
        sort(ALL(indice));
        auto a = front[i];
        REP(k, indice.size()) {
            score += a.first * abs(indice[indice.size()-k-1]-(i+k));
        }
        
        i = j-1;
    }
    cout << score << endl;
}
 
