#include <bits/stdc++.h>
using namespace std;
int n, a[1005], dp[2001][2001];
int  main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; ++i) dp[i][i] = a[i] * n;
	for (int len = 2; len <= n; len++) {
		for (int l = 1; len + l - 1 <= n; l++) {
			int r = l + len - 1;
			int d = n - len + 1;
			dp[l][r] = max(a[l] * d + dp[l + 1][r], a[r] * d + dp[l][r - 1]);
		}
	}
	cout<<dp[1][n];
	return 0;
}

救命！