#include <bits/stdc++.h>
using namespace std;
vector<pair<long long, long long> > dat;
long long N;
long long ch(long long ct, long long ans, long long ct1, long long ct2) {
  for (long long(i) = long long(ct); (i) < long long(N); (i)++) {
    long long buf = dat[i].second;
    if (((buf - ct1) > (0) ? (buf - ct1) : -(buf - ct1)) ==
        ((buf - ct2) > (0) ? (buf - ct2) : -(buf - ct2))) {
      long long buf1, buf2;
      buf1 = ch(
          i + 1,
          ans + ((buf - ct1) > (0) ? (buf - ct1) : -(buf - ct1)) * dat[i].first,
          ct1 + 1, ct2);
      buf2 = ch(
          i + 1,
          ans + ((buf - ct2) > (0) ? (buf - ct2) : -(buf - ct2)) * dat[i].first,
          ct1, ct2 - 1);
      ans = ((buf1) > (buf2) ? (buf1) : (buf2));
      break;
    } else if (((buf - ct1) > (0) ? (buf - ct1) : -(buf - ct1)) >
               ((buf - ct2) > (0) ? (buf - ct2) : -(buf - ct2))) {
      ans += ((buf - ct1) > (0) ? (buf - ct1) : -(buf - ct1)) * dat[i].first;
      ct1++;
    } else {
      ans += ((buf - ct2) > (0) ? (buf - ct2) : -(buf - ct2)) * dat[i].first;
      ct2--;
    }
    cout << (ct) << " ";
    cout << (ans) << endl;
  }
  return ans;
}
int main() {
  cin >> N;
  long long ans = 0;
  vector<long long> rui(N + 1);
  for (long long(i) = long long(0); (i) < long long(N); (i)++) {
    long long a;
    cin >> a;
    dat.emplace_back(pair<long long, long long>(a, i));
    rui[i + 1] = rui[i] + a;
  }
  vector<pair<long long, long long> > A, B;
  for (long long(i) = long long(0); (i) < long long(N); (i)++) {
    if (rui[i] > (rui[N] - rui[i + 1])) {
      A.emplace_back(dat[i]);
    } else {
      B.emplace_back(dat[i]);
    }
  }
  sort(A.begin(), A.end(), std::greater<pair<long long, long long> >());
  sort(B.begin(), B.end(), std::greater<pair<long long, long long> >());
  for (long long(i) = long long(0); (i) < long long(A.size()); (i)++) {
    ans += A[i].first *
           ((i - A[i].second) > (0) ? (i - A[i].second) : -(i - A[i].second));
  }
  for (long long(i) = long long(0); (i) < long long(B.size()); (i)++) {
    ans += B[i].first * (((N - i - 1) - B[i].second) > (0)
                             ? ((N - i - 1) - B[i].second)
                             : -((N - i - 1) - B[i].second));
  }
  cout << (ans) << endl;
  return 0;
}
