#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    cin >> A.at(i);
  }
  vector<pair<int, int>> B(N);
  for (int i = 0; i < N; ++i) {
    B[i] = make_pair(A.at(i), i);
  }
  sort(B.begin(), B.end());
  int menL = 0, menR = 0;
  int lngL = 0, lngR = 0;
  int res = 0;
  for (int i = N - 1; i >= 0; --i) {
    int happy = B.at(i).first;
    int pos = B.at(i).second;
    char W;
    lngL = pos - menL;
    lngR = N - 1 - pos - menR;
    if (lngL > lngR) {
      ++menL;
      res = res + lngL * happy;
      W = 'L';
    } else if (lngL < lngR) {
      ++menR;
      res = res + lngR * happy;
      W = 'R';
    } else {
      int next_pos = B.at(i - 1).second;
      if (next_pos > pos) {
        ++menR;
        res = res + lngR * happy;
        W = 'R';
      } else {
        ++menL;
        res = res + lngL * happy;
        W = 'L';
      }
    }
  }
  cout << res << endl;
  return 0;
}
