#include<bits/stdc++.h>
using namespace std;
int n,a[2004],dp[2004][2004];
int main(){
	freopen("treats.in","r",stdin);
	freopen("treats.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		dp[i][i]=a[i]*n;
	}
	for(int l=2;l<=n;l++){
		for(int i=1;i+l-1<=n;i++){
			int j=i+l-1;
			dp[i][j]=max(dp[i+1][j]+a[i]*(n-l+1),dp[i][j-1]+a[j]*(n-l+1));
		}
	}
	cout<<dp[1][n]<<endl;
	return 0;
}