#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;
template<int MOD> struct Fp {
  long long val;
  constexpr Fp(long long v = 0) noexcept : val(v% MOD) {
    if (val < 0) val += MOD;
  }
  constexpr int getmod() { return MOD; }
  constexpr Fp operator - () const noexcept {
    return val ? MOD - val : 0;
  }
  constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
  constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
  constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
  constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
  constexpr Fp& operator += (const Fp& r) noexcept {
    val += r.val;
    if (val >= MOD) val -= MOD;
    return *this;
  }
  constexpr Fp& operator -= (const Fp& r) noexcept {
    val -= r.val;
    if (val < 0) val += MOD;
    return *this;
  }
  constexpr Fp& operator *= (const Fp& r) noexcept {
    val = val * r.val % MOD;
    return *this;
  }
  constexpr Fp& operator /= (const Fp& r) noexcept {
    long long a = r.val, b = MOD, u = 1, v = 0;
    while (b) {
      long long t = a / b;
      a -= t * b; swap(a, b);
      u -= t * v; swap(u, v);
    }
    val = val * u % MOD;
    if (val < 0) val += MOD;
    return *this;
  }
  constexpr bool operator == (const Fp& r) const noexcept {
    return this->val == r.val;
  }
  constexpr bool operator != (const Fp& r) const noexcept {
    return this->val != r.val;
  }
  friend constexpr ostream& operator << (ostream& os, const Fp<MOD>& x) noexcept {
    return os << x.val;
  }
  friend constexpr Fp<MOD> modpow(const Fp<MOD>& a, long long n) noexcept {
    if (n == 0) return 1;
    auto t = modpow(a, n / 2);
    t = t * t;
    if (n & 1) t = t * a;
    return t;
  }
};

constexpr int MOD = 1000000007;

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i64 = int64_t;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = (b-1); i >= a; i--)
#define RF0(i,b) RFO(i,0,b)
#define F first
#define S second

/*
E: Active Infants
　はじめ左から i 番目にいる幼児の移動先を pi とすると、求めるものは Ai ∗ |i − pi
| を足し合わ
せた値の最大値になります。|x − y| = max(x − y, y − x) であることから、” Ai ∗ |i − pi
| をスコア
に足す” と言う代わりに ” Ai ∗ (i − p[i]) と Ai ∗ (p[i] − i) の好きな方を選んでスコアに足す” と言い
換えても同値な問題になります。
すると、Ai ∗ (i − p[i]) の方を選んだ添字 i の集合に対しては Ai の値の大きい方から pi を
1, 2, 3, . . . とし、Ai ∗ (p[i] − i) の方を選んだ添字 i の集合に対しては Ai の大きい方から pi を
N, N − 1, N − 2, . . . とするのが最適だということが言えます。
以上のことを踏まえれば、原始的な動的計画法を用いることで O(N2
) の計算量で答えを求めるこ
とができます。具体的には、DP[x][y] を活発度の高い方から x + y 人を既に配置しそのうち x 人で
は Ai ∗ (i − p[i]) を選択し y 人では Ai ∗ (p[i] − i) を選択したときのスコアの最大値と定義し、x + y
の昇順に計算していけば良いです。
*/

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N;
  cin >> N;
  vector<int> A(N);
  F0R(i, N) {
    cin >> A[i];
  }

  // index の配列
  vector<int> indices(N);
  iota(indices.begin(), indices.end(), 0);

  sort(indices.begin(), indices.end(), [&A](int i1, int i2) {
    return A[i1] > A[i2];
  });

  vector<vector<i64>> dp(N + 1);

  // 左に動かす数
  F0R(x, N + 1) {

    int ymax = N - x + 1;
    dp[x].reserve(ymax);

    if (x == 0) {
      dp[x].push_back(0);
    }
    else {
      auto i = indices[x - 1];
      dp[x].push_back(dp[x - 1][0] + (i64)A[i] * (i - x + 1));
    }
    //cout << dp[x][0] << ' ';
  }
  //cout << '\n';

  // 右に動かす数
  FOR(y, 1, N + 1) {

    auto i = indices[y - 1];
    dp[0].push_back(dp[0][y - 1] + (i64)(N - i - y) * A[i]);
    //cout << dp[0][y] << ' ';
  }
  //cout << '\n';


  i64 max = -1;

  // 左に動かす数
  FOR(x, 1, N + 1) {

    int ymax = N - x + 1;

    // 右に動かす数
    FOR(y, 1, ymax) {

      // 今回使う数値のindex
      auto i = indices[x + y - 1];

      dp[x].push_back(std::max(
        dp[x - 1][y] + (i64)A[i] * (i - x + 1),
        dp[x][y - 1] + (i64)A[i] * (N - i - y)
      ));
      //cout << dp[x][y] << ' ';
    }

    if (dp[x][ymax - 1] > max) {
      max = dp[x][ymax - 1];
    }
  }
  //cout << '\n';

#if 0
  // Print out dp
  F0R(x, N + 1) {
    F0R(y, dp[x].size()) {
      cout << dp[x][y] << ' ';
    }
    cout << '\n';
  }
#endif

  cout << max;
}


Measured memory_bytes: 19376