#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;
template <typename T>
class SegmentTree {
  using F = function<T(T, T)>;
  int n;
  F f;
  T t;
  vector<T> dat;

 public:
  SegmentTree(F f, T t) : f(f), t(t) {}
  void init(int n_) {
    n = 1;
    while (n < n_) n <<= 1;
    dat.assign(n << 1, t);
  }
  void build(const vector<T> &v) {
    auto n_ = (int)v.size();
    init(n_);
    for (int i = 0; i < n_; i++) dat[n + i] = v[i];
    for (int i = n - 1; i > 0; i--)
      dat[i] = f(dat[(i << 1) | 0], dat[(i << 1) | 1]);
  }
  void set_val(int k, T x) {
    dat[k += n] = x;
    while (k >>= 1) dat[k] = f(dat[(k << 1) | 0], dat[(k << 1) | 1]);
  }
  T query(int a, int b) {
    T vl = t, vr = t;
    for (int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) vl = f(vl, dat[l++]);
      if (r & 1) vr = f(dat[--r], vr);
    }
    return f(vl, vr);
  }
};
int main() {
  cin.sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  auto f = [](long long a, long long b) { return a + b; };
  SegmentTree<long long> seg(f, 0LL);
  seg.build(vector<long long>(n, 0LL));
  vector<pair<long long, int> > a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i].first;
    a[i].second = i;
    seg.set_val(i, a[i].first);
  }
  sort(a.begin(), a.end(), greater<pair<long long, int> >());
  long long ans = 0;
  int l = 0, r = n - 1;
  for (int i = 0; i < n; i++) {
    long long val = a[i].first;
    int idx = a[i].second;
    long long left = seg.query(0, idx);
    long long right = seg.query(idx + 1, n);
    if (left > val + right) {
      ans += val * (long long)abs(l - idx);
      l++;
    } else if (left + val < right) {
      ans += val * (long long)abs(r - idx);
      r--;
    } else {
      if (abs(l - idx) > abs(r - idx)) {
        ans += val * (long long)abs(l - idx);
        l++;
      } else {
        ans += val * (long long)abs(r - idx);
        r--;
      }
    }
    seg.set_val(idx, 0);
  }
  cout << ans << "\n";
  return 0;
}
