#include <bits/stdc++.h>
const int INF = (int)1e9 + 10;
const long long MOD = (long long)1e9 + 7;
const long long LINF = (long long)4e18 + 20;
const long double PI = acos(-1.0);
const double EPS = 1e-9;
using namespace ::std;
void chmax(long long& a, long long b) { a = max(a, b); }
void chmin(long long& a, long long b) { a = min(a, b); }
class BITree {
  int N;
  vector<long long> bit;

 public:
  BITree(int n) {
    N = n;
    bit = vector<long long>(N + 1, 0);
  }
  void add(int a, long long w) {
    if (a <= 0 || N < a) return;
    for (int i = a; i <= N; i += i & -i) {
      bit[i] += w;
    }
  }
  long long sum(int a) {
    long long ret = 0;
    if (a > N) a = N;
    for (int i = a; i > 0; i -= i & -i) {
      ret += bit[i];
    }
    return ret;
  }
  long long sum(int a, int b) {
    long long ret = 0;
    ret = sum(b) - sum(a - 1);
    return ret;
  }
};
void solve() {
  int N;
  cin >> N;
  vector<pair<long long, long long>> A(N);
  BITree bitS(N), bit1(N);
  pair<long long, long long> temp;
  for (int i = 0; i < N; ++i) {
    cin >> temp.first;
    temp.second = i + 1;
    bitS.add(i + 1, temp.first);
    bit1.add(i + 1, 1);
    A[i] = temp;
  }
  sort(A.begin(), A.end());
  reverse(A.begin(), A.end());
  long long ans = 0;
  int Lindex = 1;
  int Rindex = N;
  for (int i = 0; i < N; ++i) {
    int ter = A[i].second;
    long long L = bitS.sum(1, ter - 1);
    long long R = bitS.sum(ter + 1, N);
    int long long = bit1.sum(1, ter - 1);
    int RR = bit1.sum(ter + 1, N);
    int now = Lindex - 1 + long long + 1;
    if (now < ter) {
      ans += A[i].first * abs(Lindex - ter);
      ++Lindex;
      bitS.add(ter, -A[i].first);
      bit1.add(ter, -1);
    } else if (now > ter) {
      ans += A[i].first * abs(Rindex - ter);
      --Rindex;
      bitS.add(ter, -A[i].first);
      bit1.add(ter, -1);
    } else {
      if (L > R) {
        ans += A[i].first * abs(Lindex - ter);
        ++Lindex;
        bitS.add(ter, -A[i].first);
        bit1.add(ter, -1);
      } else {
        ans += A[i].first * abs(Rindex - ter);
        --Rindex;
        bitS.add(ter, -A[i].first);
        bit1.add(ter, -1);
      }
    }
  }
  cout << ans << endl;
}
signed main(void) {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  std::cout << std::fixed;
  cout << setprecision(16);
  solve();
}
