#include <bits/stdc++.h>
template <class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
using namespace std;
int main() {
  long long N, ans = 0ll, cnt = 0ll;
  cin >> N;
  long long A[N], DP[N + 1][N + 1];
  for (int i = (0); i < (N); ++i) cin >> A[i];
  for (int i = (0); i < (N + 1); ++i) {
    for (int j = (0); j < (N + 1); ++j) {
      DP[i][j] = 0;
    }
  }
  vector<pair<long long, long long>> P;
  for (int i = (0); i < (N); ++i) P.push_back(make_pair(A[i], i));
  sort((P).begin(), (P).end());
  reverse((P).begin(), (P).end());
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j <= i; ++j) {
      DP[j + 1][i - j] = max(DP[j + 1][i - j],
                             DP[j][i - j] + P[i].first * abs(P[i].second - j));
      DP[j][i - j + 1] =
          max(DP[j][i - j + 1],
              DP[j][i - j] + P[i].first * abs(P[i].second - N + i - j + 1));
    }
  }
  for (int i = 0; i <= N; ++i) {
    if (ans < DP[i][N - i]) ans = DP[i][N - i];
  }
  for (int i = 0; i <= N; ++i) {
    for (int j = 0; j <= N; ++j) {
      cout << DP[i][j] << '\n';
    }
  }
  cout << ans << '\n';
  return 0;
}
