勿喷

#include<bits/stdc++.h>
using namespace std;
int dp[2005][2005],m[2005],n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>m[i];
	}
	dp[1][n]=0;
	for(int len=n-1;len>=1;len--){
		for(int i=1;i+len-1<=n;i++){
			int j=i+len-1;
			int get=n-len;
			dp[i][j]=max(dp[i][j+1]+m[j]*get,max(dp[i][j],dp[i-1][j]+m[i]*get));
		} 
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,dp[i][i]+m[i]*n);
	}
	cout<<ans;
	return 0;
}