#include <bits/stdc++.h>
using namespace std;
const long long N = 1e2 + 10;
long long a[N];
long long dp[N][2000][3];
signed main() {
  long long n;
  scanf("%lld", &n);
  for (long long i = 1; i <= n; ++i) {
    scanf("%lld", &a[i]);
  }
  memset(dp, -0x7f, sizeof(dp));
  for (long long j = 0; j <= 1000 / a[1]; ++j) {
    dp[1][j][1] = -1 * j * a[1];
  }
  dp[1][0][0] = 0;
  dp[1][0][2] = 0;
  long long res = 0;
  for (long long k = 2; k <= n; ++k) {
    for (long long i = 0; i <= 50; ++i) {
      dp[k][i][0] = max(dp[k - 1][i][1], max(dp[k - 1][i][2], dp[k - 1][i][0]));
    }
    for (long long i = 0; i <= 50; ++i) {
      for (long long j = i + 1; j <= 50; ++j) {
        if (dp[k][i][0] - (j - i) * a[k] + 1000 >= 0)
          dp[k][j][1] = max(dp[k][j][1], dp[k][i][0] - (j - i) * a[k]);
        if (dp[k][j][0] + 1000 >= 0)
          dp[k][i][2] = max(dp[k][i][2], dp[k][j][0] + (j - i) * a[k]);
      }
    }
    res = max(res, max(dp[k][0][0], max(dp[k][0][1], dp[k][0][2])));
  }
  cout << 1000 + res;
  return 0;
}
