#include<cstdio>

#include<cstring>

#include<cmath>

#include<stack>

#include<vector>

#include<string>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=+;

int dp[maxn][maxn];

int a[maxn];

int n;

int MAX(int a,int b)

{

    if(a>b) return a;

    return b;

}

int main()

{

    scanf("%d",&n);

    {

        for(int i=; i<=n; i++) scanf("%lld",&a[i]);

        memset(dp,,sizeof dp);

        int c=n;

        for(int i=; i<=n; i++) dp[i][i]=a[i]*c;

        c--;

        int ans=;

        for(int i=; i<=n; i++) //区间长度

        {

            for(int j=; j<=n; j++) //起点

            {

                int st=j,en=i+j-;

                if(en>n) break;

                dp[st][en]=MAX(dp[st+][en]+c*a[st],dp[st][en-]+c*a[en]);

            }

            c--;

        }

        printf("%d\n",dp[][n]);

    }

    return ;

}