#include<stdio.h>
__int64 mmg[3000][3000][2];
__int64 xiaocai[3000];
__int64 k;
__int64 f(__int64 a,__int64 b)
{
	__int64 m,n,t;
	if(mmg[a][b][1]==1) return mmg[a][b][0];
	t=a+k-b;
	if(a==b) return xiaocai[a]*t;
	if(mmg[a+1][b][1]==1) m=mmg[a+1][b][0];
	else m=xiaocai[a]*t+f(a+1,b);
	if(mmg[a][b-1][1]==1) n=mmg[a][b-1][0];
	else n=xiaocai[b]*t+f(a,b-1);
	mmg[a][b][0]=m>n?m:n;
	mmg[a][b][1]=1;
	return mmg[a][b][0];
}
__int64 main()
{
	__int64 i,j;
	while(scanf("%I64d",&k)!=EOF){
		for(i=0;i<k;i++) scanf("%d",&xiaocai[i]);
		for(i=0;i<k;i++)

			for(j=0;j<k;j++) mmg[i][j][1]=0;
		printf("%I64d\n",f(0,k-1));
	}
}