#include<bits/stdc++.h>
using namespace std;

// [1] n-纪念品的数量；arr数组-存储每个纪念品的初始价格（下标1~n）
int n,arr[2100];
// [2] dp[l][r]-区间[l, r]内的纪念品，在剩余天数里卖出能获得的最大收益
int dp[2100][2100]={};

int main(){
    // 问题分析：区间DP问题，每天只能卖当前区间最左/最右的纪念品，第C天卖出价格为p_i×C，求N天卖完所有纪念品的最大收益
    // 解题步骤：1.初始化单个纪念品的区间（最后一天卖出，价格为p_i×n）；2.按区间长度从小到大动态规划，计算每个区间的最大收益；
    //          3.状态转移：选择卖最左或最右的纪念品，收益为当前卖出价格+剩余区间的最大收益；4.最终dp[1][n]即为整个区间的最大收益
    
    cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i];  // [3] 读取每个纪念品的初始价格
    
    // 1. 初始化：长度为1的区间（单个纪念品），会在第n天（最后一天）卖出，价格为arr[i]×n
    for(int i=1;i<=n;i++) dp[i][i]=arr[i]*n;  // [4] 区间[i,i]只有一个纪念品，直接计算最后一天的收益
    
    // 区间DP核心循环：按区间长度从小到大计算（len为区间长度，从2到n）
    for(int len=2;len<=n;len++){
        // 3. k-当前区间对应的卖出天数：总天数n，区间长度为len时，该区间的纪念品会在第k天开始卖（k = n - len + 1）
        int k=n-len+1; 
        // 遍历所有长度为len的区间的左端点l
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;  // [5] 计算当前区间的右端点r
            // 4. 状态转移：选择卖最左或最右的纪念品，取收益较大的情况
            // 卖左端点l：收益=arr[l]×k（第k天卖出l） + 剩余区间[l+1, r]的最大收益dp[l+1][r]
            // 卖右端点r：收益=arr[r]×k（第k天卖出r） + 剩余区间[l, r-1]的最大收益dp[l][r-1]
            dp[l][r]=max(dp[l+1][r]+arr[l]*k,dp[l][r-1]+arr[r]*k); 
        }
    }
    cout<<dp[1][n];  // [6] 输出整个区间[1, n]的最大收益，即卖完所有纪念品的最大收入
    return 0;
}