#include <bits/stdc++.h>
using namespace std;
const int MAX = 5100;
const int MOD = 1000000007;
vector<vector<long long> > dp(MAX, vector<long long>(MAX, -1000000000));
int main() {
  long long N;
  cin >> N;
  vector<pair<int, int> > a(N);
  for (int i = 0; i < N; i++) {
    cin >> a[i].first;
    a[i].second = i + 1;
  }
  sort(a.begin(), a.end(), greater<pair<int, int> >());
  dp[0][0] = 0;
  for (int i = 0; i < N + 1; i++) {
    for (int j = 0; j < N + 1; j++) {
      if (i == 0) {
        dp[i][j + 1] = dp[i][j] + a[j].first * abs(a[j].second - (N - j));
      } else {
        if (j == 0) {
          dp[i][j] = dp[i - 1][j] + a[i - 1].first * abs(a[i - 1].second - i);
        } else {
          dp[i][j] = max(
              dp[i - 1][j] + a[i + j - 1].first * abs(a[i + j - 1].second - i),
              dp[i][j - 1] + a[i + j - 1].first *
                                 abs(a[i + j - 1].second - (N - (j - 1))));
        }
      }
    }
  }
  for (int i = 0; i < N + 1; i++) {
    for (int j = 0; j < N + 1; j++) {
      cout << dp[i][j] << " ";
    }
    cout << endl;
  }
  long long ans = 0;
  for (int i = 0; i < N + 1; i++) {
    ans = max(ans, dp[i][N - i]);
  }
  cout << ans << endl;
}
