#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e3 + 5;
void fio() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
long long dp[MAXN][MAXN];
int main() {
  fio();
  int n;
  cin >> n;
  vector<pair<long long, long long> > v(n + 1);
  v[0].first = 1e18;
  for (int i = 1; i <= n; i++) {
    cin >> v[i].first;
    v[i].second = i;
  }
  sort(v.begin(), v.end(), greater<pair<long long, long long> >());
  for (int i = 1; i <= n; i++) {
    auto u = v[i];
    cout << u.first << " ";
    for (long long j = 0; j < i; j++) {
      long long l = j;
      long long r = (i - 1 - j);
      dp[l + 1][r] =
          max(dp[l + 1][r], dp[l][r] + abs(l + 1 - u.second) * u.first);
      dp[l][r + 1] =
          max(dp[l][r + 1], dp[l][r] + abs(n - r - u.second) * u.first);
    }
  }
  cout << endl;
  long long an = 0;
  for (int i = 0; i < (n + 1); i++) an = max(an, dp[i][n - i]);
  cout << an << endl;
  return 0;
}
