function sort(A,l,r,tmp,mid,il,ir)#[l,r)
{
	if(r-l==2)
	{
		if(sort_cmp(A[l+1],A[l]))
		{
			tmp=A[l];
			A[l]=A[l+1];
			A[l+1]=tmp;
		}
	}
	else if(r-l>2)
	{
		mid=int((l+r)/2);
		if(sort_cmp(A[mid],A[l]))
		{
			tmp=A[mid];
			A[mid]=A[l];
			A[l]=tmp;
		}
		if(sort_cmp(A[r-1],A[mid]))
		{
			tmp=A[r-1];
			A[r-1]=A[mid];
			A[mid]=tmp;
			if(sort_cmp(A[mid],A[l]))
			{
				tmp=A[mid];
				A[mid]=A[l];
				A[l]=tmp;
			}
		}
		il=l;
		ir=r-1;
		while(il<=ir)
		{
			while(sort_cmp(A[il],A[mid]))il++;
			while(sort_cmp(A[mid],A[ir]))ir--;
			if(il<ir)
			{
				tmp=A[il];
				A[il]=A[ir];
				A[ir]=tmp;
				if(mid==il)mid=ir;
				else if(mid==ir)mid=il;
				il++;
				ir--;
			}
			else if(il==ir)
			{
				il++;
				ir--;
			}
		}
		sort(A,l,il);
		sort(A,il,r);
	}
}
function sort_cmp(a,b)#bool(a<b)
{
	return A[a]>A[b];
}
NR==1{N=$1}
NR==2{
	for(i=1;i<=N;i++)
	{
		A[i]=+$i;
		id[i]=i;
	}
}
function max(a,b){return a<b?b:a}
function abs(a){return a<0?-a:a}
END{
	sort(id,1,N+1);
	for(i=1;i<=N;i++)
	{
		a=A[jd=id[i]];
		for(j=1;j<=i;j++)
		{
			k=N+1-(i-j);
			dp[j+1][k]=max(dp[j+1][k],dp[j][k]+a*abs(jd-j));
			dp[j][k-1]=max(dp[j][k-1],dp[j][k]+a*abs(jd-(k-1)));
		}
	}
	ans=0
	for(i=1;i<=N+1;i++)ans=max(ans,dp[i][i]);
	print ans
}
