#include <bits/stdc++.h>
template <class T>
inline T chmax(T &a, const T b) {
  return a = (a < b) ? b : a;
}
template <class T>
inline T chmin(T &a, const T b) {
  return a = (a > b) ? b : a;
}
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const ll MOD = 1000000007;
const ll INF = 1e18;
const double PI = acos(-1);
using namespace std;
struct INIT {
  INIT() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
  }
} INIT;
template <typename T>
struct bit {
  vector<T> data;
  bit(ll sz) { data.assign(++sz, 0); }
  bit(ll sz, ll v) {
    data.assign(++sz, v);
    for (ll i = 0; i < ll(sz); ++i) data[i + (i & -i)] += data[i];
  }
  T sum(ll k) {
    T ret = 0;
    for (++k; k > 0; k -= k & -k) ret += data[k];
    return ret;
  }
  void add(ll k, T x) {
    for (++k; k < data.size(); k += k & -k) data[k] += x;
  }
};
template <typename Monoid>
struct SegmentTree {
  using F = function<Monoid(Monoid, Monoid)>;
  ll sz;
  vector<Monoid> seg;
  const F f;
  const Monoid M1;
  SegmentTree(ll n, const F f, const Monoid &M1) : f(f), M1(M1) {
    sz = 1;
    while (sz < n) sz <<= 1;
    seg.assign(2 * sz, M1);
  }
  void set(ll k, const Monoid &x) { seg[k + sz] = x; }
  void build() {
    for (ll k = sz - 1; k > 0; k--) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }
  void update(ll k, const Monoid &x) {
    k += sz;
    seg[k] = x;
    while (k >>= 1) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }
  Monoid query(ll a, ll b) {
    Monoid L = M1, R = M1;
    for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if (a & 1) L = f(L, seg[a++]);
      if (b & 1) R = f(seg[--b], R);
    }
    return f(L, R);
  }
  Monoid operator[](const ll &k) const { return seg[k + sz]; }
  template <typename C>
  ll find_subtree(ll a, const C &check, Monoid &M, bool type) {
    while (a < sz) {
      Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);
      if (check(nxt))
        a = 2 * a + type;
      else
        M = nxt, a = 2 * a + 1 - type;
    }
    return a - sz;
  }
  template <typename C>
  ll find_first(ll a, const C &check) {
    Monoid L = M1;
    if (a <= 0) {
      if (check(f(L, seg[1]))) return find_subtree(1, check, L, false);
      return -1;
    }
    ll b = sz;
    for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if (a & 1) {
        Monoid nxt = f(L, seg[a]);
        if (check(nxt)) return find_subtree(a, check, L, false);
        L = nxt;
        ++a;
      }
    }
    return -1;
  }
  template <typename C>
  ll find_last(ll b, const C &check) {
    Monoid R = M1;
    if (b >= sz) {
      if (check(f(seg[1], R))) return find_subtree(1, check, R, true);
      return -1;
    }
    ll a = sz;
    for (b += sz; a < b; a >>= 1, b >>= 1) {
      if (b & 1) {
        Monoid nxt = f(seg[--b], R);
        if (check(nxt)) return find_subtree(b, check, R, true);
        R = nxt;
      }
    }
    return -1;
  }
};
signed main() {
  ll N;
  cin >> N;
  vector<ll> A(N);
  for (ll i = 0; i < ll(N); ++i) cin >> A[i];
  bit<ll> bit(N);
  for (ll i = 0; i < ll(N); ++i) bit.add(i, A[i]);
  SegmentTree<ll> seg(
      N, [](ll a, ll b) { return max(a, b); }, -INF);
  for (ll i = 0; i < ll(N); ++i) seg.set(i, A[i]);
  seg.build();
  vector<bool> used(N, false);
  ll left = 0, right = N - 1;
  ll ans = 0;
  bool mitei = true;
  for (ll i = 0; i < ll(N); ++i) {
    pair<ll, ll> MAX(0, 0);
    for (ll j = 0; j < ll(N); ++j) {
      if (used[j]) continue;
      if (MAX.first < A[j]) MAX = {A[j], j};
    }
    used[MAX.second] = true;
    ll l = abs(MAX.second - left);
    ll r = abs(right - MAX.second);
    ll lll = bit.sum(MAX.second - 1);
    ll rrr = bit.sum(N - 1) - bit.sum(MAX.second);
    if (r != l && max(lll, rrr) < MAX.first) {
      if (l > r) {
        ans += l * MAX.first;
        left++;
      } else {
        ans += r * MAX.first;
        right--;
      }
    } else {
      if (lll == rrr) {
        if (seg.query(0, i) < seg.query(i + 1, N)) {
          ans += r * MAX.first;
          right--;
        } else {
          ans += l * MAX.first;
          left++;
        }
      } else if (lll < rrr) {
        ans += r * MAX.first;
        right--;
      } else {
        ans += l * MAX.first;
        left++;
      }
    }
    bit.add(MAX.second, -MAX.first);
  }
  cout << ans << "\n";
  return 0;
}
