#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <typename T, typename Query>
class segment_tree {
 private:
  size_t size_;
  std::vector<T> tree_;
  Query query_;
  T invalid_val_;

 public:
  segment_tree(size_t size, T invalid_val) {
    size_ = 1;
    while (size_ < size) size_ *= 2;
    invalid_val_ = invalid_val;
    tree_.resize(size_ * 2, invalid_val_);
  }
  template <typename Iter>
  segment_tree(Iter begin, Iter end, T invalid_val)
      : segment_tree(end - begin, invalid_val) {
    for (auto it = begin; it != end; ++it) {
      tree_[size_ + it - begin] = *it;
    }
    for (size_t i = size_ - 1; i > 0; i--) {
      tree_[i] = query_(tree_[i * 2], tree_[i * 2 + 1]);
    }
  }
  T operator[](size_t index) const { return tree_[size_ + index]; }
  void set(size_t index, T val) {
    auto i = size_ + index;
    tree_[i] = val;
    i /= 2;
    while (i > 0) {
      tree_[i] = query_(tree_[i * 2], tree_[i * 2 + 1]);
      i /= 2;
    }
  }
  T query(size_t l, size_t r) const { return _query(l, r, 1, 0, size_); }

 private:
  T _query(size_t l, size_t r, size_t _d, size_t _l, size_t _r) const {
    if (r <= _l or _r <= l) {
      return invalid_val_;
    } else if (l <= _l and _r <= r) {
      return tree_[_d];
    } else {
      auto c = (_l + _r) / 2;
      return query_(_query(l, r, _d * 2, _l, c),
                    _query(l, r, _d * 2 + 1, c, _r));
    }
  }
};
int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  struct sum {
    ll operator()(ll a, ll b) const { return a + b; }
  };
  segment_tree<ll, sum> st(n, 0);
  vector<pair<int, int>> A(n);
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    st.set(i, a);
    A[i] = {a, i};
  }
  sort(A.rbegin(), A.rend());
  ll ans = 0;
  int l = 0, r = n - 1;
  for (auto a : A) {
    auto lhs = abs(a.second - l) - st.query(a.second + 1, r + 1);
    auto rhs = abs(a.second - r) - st.query(l, a.second);
    if (lhs >= rhs) {
      ans += a.first * abs(a.second - l);
      ++l;
    } else {
      ans += a.first * (abs(a.second - r));
      --r;
    }
    st.set(a.second, 0);
  }
  cout << ans << endl;
  return 0;
}
