#include<bits/stdc++.h>
using namespace std;
int n,dp[1001][1001],v[1001];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>v[i];
	}
	for(int i=1;i<=n;i++){
		dp[i][i]=v[i]*n;
	}
	for(int len=2;len<=n;len++){
		for(int l=1;l<=n;l++){
			int r=l+len-1;
			if(r>n)break;
			dp[l][r]=max(dp[l+1][r]+v[l]*(n-len+1),dp[l][r-1]+v[r]*(n-len+1));
		}
	}
	cout<<dp[1][n];
}