#include<iostream> 
#include<cstdio>
using namespace std;
int n,f[2005][2005];
char ch;
inline void read(int &x){x=0;ch=getchar();while(ch<48||ch>57) ch=getchar();while(ch>47&&ch<58) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();}
int main()
{
	freopen("treats.in","r",stdin); freopen("treats.out","w",stdout);
	read(n);
	for(int i=1;i<=n;++i) read(f[i][i-1]),f[i][i]=f[i][i-1]*n;
	for(int i=1;i<n;++i) for(int j=1;j<=n-i;++j) f[j][j+i]=max(f[j][j+i],max(f[j][j+i-1]+f[j+i][j+i-1]*(n-i),f[j+1][j+i]+f[j][j-1]*(n-i)));
	printf("%d\n",f[1][n]);
	return 0;
}