1 //2017-04-06
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 
 9 const int N = 2005;
10 int v[N], n, dp[N][N];//dp[l][r]表示区间l~r间的最大收益
11 //状态转移方程：dp[l][r] = max(dp[l+1][r]+day*v[l], dp[l][r-1]+day*v[r])
12 
13 int dfs(int l, int r, int day)
14 {
15     if(l > r)return 0;
16     if(dp[l][r])return dp[l][r];
17     if(l == r)return dp[l][r] = day*v[l];
18     return dp[l][r] = max(dfs(l+1, r, day+1)+day*v[l], dfs(l, r-1, day+1)+day*v[r]);
19 }
20 
21 int main()
22 {
23     while(scanf("%d", &n)!=EOF)
24     {
25         for(int i = 0; i < n; i++)
26               scanf("%d", &v[i]);
27         memset(dp, 0, sizeof(dp));
28         int ans = dfs(0, n-1, 1);
29         printf("%d\n", ans);
30     }
31 
32     return 0;
33 }