#include <bits/stdc++.h>
using namespace std;
int n;
long long a[2010];
long long sum[2010];
bool visit[2010];
vector<pair<long long, int> > v;
long long res;
int main() {
  cin >> n;
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
    v.push_back(make_pair(-a[i], i));
    res += max(i, n - 1 - i) * a[i];
  }
  sort(v.begin(), v.end());
  for (int i = 0; i < n - 1; i++) {
    int x = v[i].second;
    fill(sum, sum + n, 0);
    int l = 0, r = n - 1, li, ri;
    while (visit[l]) l++;
    while (visit[r]) r--;
    li = l + 1, ri = r - 1;
    while (visit[li]) li++;
    while (visit[ri]) ri--;
    for (int j = i + 1; j < n; j++)
      sum[(abs(v[j].second - l) > abs(r - v[j].second) ? l : r)] -=
          (max(abs(v[j].second - l), abs(r - v[j].second)) -
           max(abs(v[j].second - li), abs(ri - v[j].second))) *
          v[j].first;
    int t = -1;
    for (int j = 0; j < n; j++)
      if (!visit[j] &&
          (t == -1 || abs(v[i].second - j) * v[i].first - sum[j] <
                          abs(v[i].second - t) * v[i].first - sum[t]))
        t = j;
    res -= sum[t];
    visit[t] = 1;
  }
  cout << res;
  return 0;
}
