#include <bits/stdc++.h>
using namespace std;
using vi = vector<long long>;
using vvi = vector<vi>;
long long n, k, x, y;
void mysort2(vi &a, vi &b, long long flag) {
  vector<pair<long long, long long>> p(a.size());
  for (long long i = 0; i < n; i++) {
    p[i].first = a[i];
    p[i].second = b[i];
  }
  sort(p.begin(), p.end());
  if (flag == 1) {
    reverse(p.begin(), p.end());
  }
  for (long long i = 0; i < n; i++) {
    a[i] = p[i].first;
    b[i] = p[i].second;
  }
  return;
}
int main() {
  long long ans = 0;
  cin >> n;
  vi a(n), b(n), c(n), d(n), e(n);
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
    b[i] = i;
  }
  mysort2(a, b, 1);
  long long r = n - 1, l = 0;
  for (long long i = 0; i < n; i++) {
    if (abs(r - b[i]) > abs(b[i] - l)) {
      ans += abs(r - b[i]) * a[i];
      c[r] = a[i];
      d[r] = b[i];
      r--;
    } else {
      ans += abs(b[i] - l) * a[i];
      c[l] = a[i];
      d[l] = b[i];
      l++;
    }
  }
  r = n - 1;
  l = 0;
  for (long long i = 0; i < n; i++) {
    if (c[r] > c[l]) {
      long long gk = c[r] * (abs(d[r] - l) - abs(d[r] - r));
      for (long long j = l; j < r; j++) {
        gk += c[j] * (abs(d[j] - (j + 1)) - abs(d[j] - j));
      }
      if (gk > 0) {
        gk = c[r];
        long long dgk = d[r];
        for (long long j = r - 1; j >= l; j--) {
          c[j + 1] = c[j];
          d[j + 1] = d[j];
        }
        c[l] = gk;
        d[l] = dgk;
        l++;
      } else {
        r--;
      }
    } else {
      long long gk = c[l] * (abs(d[l] - r) - abs(d[l] - l));
      for (long long j = l + 1; j <= r; j++) {
        gk += c[j] * (abs(d[j] - (j - 1)) - abs(d[j] - j));
      }
      if (gk > 0) {
        gk = c[l];
        long long dgk = d[l];
        for (long long j = l; j < r; j++) {
          c[j] = c[j + 1];
          d[j] = d[j + 1];
        }
        c[r] = gk;
        d[r] = dgk;
        r--;
      } else {
        l++;
      }
    }
  }
  ans = 0;
  for (long long i = 0; i < n; i++) {
    ans += c[i] * abs(d[i] - i);
  }
  cout << ans << endl;
  return 0;
}
