#include <bits/stdc++.h>
using namespace std;
long long maxstock = 3000;
long long initialmoney = 1000;
int32_t main() {
  long long n, i, j, k;
  cin >> n;
  long long arr[n];
  for (i = 0; i < n; i++) cin >> arr[i];
  long long dp[n][maxstock];
  for (i = 0; i < n; i++)
    for (j = 0; j < maxstock; j++) dp[i][j] = -1;
  dp[0][0] = 1000;
  for (i = 1; i < maxstock; i++) {
    dp[0][i] = max(-1ll, dp[0][i - 1] - arr[0]);
  }
  for (i = 1; i < n; i++) {
    long long ind = maxstock - 1;
    while (dp[i - 1][ind] == -1) ind--;
    for (j = 0; j <= ind; j++) {
      for (k = 0; k <= ind; k++) {
        if (j <= k) {
          dp[i][j] = max(dp[i][j], dp[i - 1][k] + (k - j) * arr[i]);
        } else {
          dp[i][j] = max(dp[i][j], dp[i - 1][k] - (j - k) * arr[i]);
        }
      }
    }
    for (j = 0; j <= ind; j++) {
      dp[i][ind + 1] = max(dp[i][ind + 1], dp[i][j] - (ind + 1 - j) * arr[i]);
    }
    for (j = ind + 2; j < maxstock; j++) {
      dp[i][j] = max(dp[i][j], dp[i][j - 1] - arr[i]);
    }
  }
  cout << dp[n - 1][0] << "\n";
}
