mxt

#include <iostream>
#define Nmax 2001
using namespace std;
int n,a[Nmax],dp[Nmax][Nmax];

int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    for(int i=1;i<=n;++i)
        dp[i][i]=n*a[i];
    int j;
    for(int k=1;k<n;++k)
        for(int i=1;i<=n-k;++i)
        {
            j=i+k;
            dp[i][j]=max((n-(j-i))*a[i]+dp[i+1][j],dp[i][j-1]+(n-(j-i))*a[j]);
        }
    cout<<dp[1][n];
    return 0;
}