#include<bits/stdc++.h>
using namespace std;

#define int long long

// #include "debug.cpp"


int maxstock = 3000;
int initialmoney = 1000;


int main(){
	int n, i, j, k;
	cin >> n;
	int arr[n];
	for(i=0; i<n; i++)
		cin >> arr[i];

	int 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=0; i<20; i++)
	// 	cout << dp[0][i] << " ";
	// cout << "\n";

	for(i=1; i<n; i++){
		int ind = maxstock-1;
		while(dp[i-1][ind] == -1)
			ind--;

		// debug("AA");
		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]);
		}



		// for(j=0; j<n; j++){
		// 	for(k=0; k<maxstock; k++){
		// 		cout << dp[j][k] << " ";
		// 	}
		// 	cout << "\n";
		// }
		// cout << "\n";

	}

	// for(i=0; i<20; i++)
	// 	cout << dp[n-1][i] << " ";
	// cout << "\n";
	cout << dp[n-1][0] << "\n";


}