//f[l][r] = (f[l+1][r]+a[l]*(n-len+1),f[l][r-1]+a[r]*(n-len+1)
#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
#define int long long
int f[N][N], n, a[N];

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i],f[i][i]=a[i]*n;
	for (int len = 2; len <= n; len++) {
		for (int l = 1; l + len - 1 <= n; l++) {
			int r = l + len - 1;
			f[l][r] = max(f[l + 1][r] + a[l] * (n - len + 1), f[l][r - 1] + a[r] * (n - len + 1));
		}
	}
	cout << f[1][n] << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 305;
int n, sum[N], f[N][N];

signed main() {
	cin >> n;
	memset(f, 0x3f, sizeof(f));
	for (int i = 1; i <= n; i++) {
		cin >> sum[i];
		sum[i] += sum[i - 1];
		f[i][i] = 0;
	}
	for (int len = 2; len <= n; len++) {
		for (int l = 1; l + len - 1 <= n; l++) {
			int r = l + len - 1;
			for (int k = l; k < r; k++) {
				f[l][r] = min(f[l][k] + f[k + 1][r] + sum[r] - sum[l - 1], f[l][r]);
			}
		}
	}
	cout << f[1][n] << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 505;
const int Mod = 1e9+7;
char s[N];
int n,m,sum[N],f[N][N][5];
signed main()
{
	//freopen("bracket3.in","r",stdin);
	cin>>n>>m;
	cin>>s+1;
	for(int i=1;i<=n;i++){
		sum[i] = sum[i-1];
		if(s[i]=='(' || s[i]==')')sum[i]++;
		if(i!=n)if((s[i]=='(' || s[i]=='?') && (s[i+1]==')' || s[i+1]=='?'))f[i][i+1][0] = 1;
	}
	for(int len=2;len<=n;len++){
		for(int l=1;l+len-1<=n;l++){
			int r = l+len-1;
			//1.(A)
			if(r-l>=2 && (s[l]=='(' || s[l]=='?') && (s[r]==')' || s[r]=='?')){
				f[l][r][0] = (f[l][r][0] + (f[l+1][r-1][0]+f[l+1][r-1][1])%Mod)%Mod;
			}
			//2.(B)
			if(r-l>=2 && r-l-1<=m && sum[r-1]-sum[l]==0 && (s[l]=='(' || s[l]=='?') && (s[r]==')' || s[r]=='?')){
				f[l][r][0] = (f[l][r][0] + ((sum[r-1]-sum[l])==0))%Mod;
			}
			//3.AB
			if(r-l>=3){
				for(int k=l;k<r;k++){
					f[l][r][1] = (f[l][r][1] + (f[l][k][0]*((f[k+1][r][0]+f[k+1][r][1])%Mod))%Mod)%Mod;
				}
			}
			//4.(AS)
			if(r-l>=4 && (s[l]=='(' || s[l]=='?') && (s[r]==')' || s[r]=='?')){
				for(int k=max(l+1,r-m-1);k<r-1;k++){
					if(r-k-1<=m)f[l][r][0] = (f[l][r][0]+((f[l+1][k][0]+f[l+1][k][1])%Mod)*((sum[r-1]-sum[k])==0))%Mod;
				}
			}
			//5.(SA)
			if(r-l>=4 && (s[l]=='(' || s[l]=='?') && (s[r]==')' || s[r]=='?')){
				for(int k=l+1;k<=min(l+m,r-2);k++){
					if(k-l<=m)f[l][r][0] = (f[l][r][0]+((f[k+1][r-1][0]+f[k+1][r-1][1])%Mod)*((sum[k]-sum[l])==0))%Mod;
				}
			}
			//6.SB
			if(r-l>=2){
				for(int k=l;k<=min(l+m-1,r-1);k++){
					f[l][r][2] = (f[l][r][2]+((f[k+1][r][0]+f[k+1][r][1])%Mod)*((sum[k]-sum[l-1])==0))%Mod;
				}
			}
			//7.ASB
			if(r-l>=4){
				for(int k=l+1;k<r-1;k++){
					f[l][r][1] = (f[l][r][1]+(((f[l][k][0])%Mod)*(f[k+1][r][2]))%Mod)%Mod;
				}
			}
		}
	}
	cout<<(f[1][n][0]+f[1][n][1])%Mod<<endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
int n, a[N], f[N][N];

int main() {
	cin >> n;
	memset(f, 0x3f, sizeof(f));
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		f[i][i] = 0;
		if (i != 1)
			f[i - 1][i] = abs(a[i] - a[i - 1]);
	}
	for (int len = 3; len <= n; len++) {
		for (int l = 1; l + len - 1 <= n; l++) {
			int r = l + len - 1;
			f[l][r] = f[l + 1][r - 1] + abs(a[l] - a[r]);
		}
	}
	for (int len = 1; len <= n; len++) {
		int minn = 0x3f3f3f3f;
		for (int l = 1; l + len - 1 <= n; l++) {
			int r = l + len - 1;
			minn = min(minn, f[l][r]);
		}
		cout << minn << " ";
	}
	return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
#include <cstdlib>
#include <iomanip>
using namespace std;
const int N = 55;
int n, m;
set<int>st;
queue<int>q;
int pos[N], a[N], sum[N], f[N][N][2];

//f[i][j][0]表示i-j区间走完 在i位置
//f[i][j][1]表示i-j区间走完 在j位置
/*
 *f[i][j][0] = f[i+1][j][0]+(pos[i+1]-pos[i])*(sum[n]-sum[j]+sum[i])
 *f[i][j][0] = f[i+1][j][1]+(pos[j]-pos[i])*(sum[n]-sum[j]+sum[i])
 *f[i][j][1] = f[i][j-1][1]+(pos[j]-pos[j-1])*(sum[n]-sum[j-1]+sum[i-1])
 *f[i][j][1] = f[i][j-1][0]+(pos[j]-pos[i])*(sum[n]-sum[j-1]+sum[i-1])
 */
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> pos[i] >> a[i];
		sum[i] = sum[i - 1] + a[i];
	}
	memset(f, 0x3f, sizeof(f));
	f[m][m][0] = 0;
	f[m][m][1] = 0;
	for (int len = 2; len <= n; len++) {
		for (int l = 1; l + len - 1 <= n; l++) {
			int r = l + len - 1;
			f[l][r][0] = min(f[l][r][0], f[l + 1][r][0] + (pos[l + 1] - pos[l]) * (sum[n] - sum[r] + sum[l]));
			f[l][r][0] = min(f[l][r][0], f[l + 1][r][1] + (pos[r] - pos[l]) * (sum[n] - sum[r] + sum[l]));
			f[l][r][1] = min(f[l][r][1], f[l][r - 1][1] + (pos[r] - pos[r - 1]) * (sum[n] - sum[r - 1] + sum[l - 1]));
			f[l][r][1] = min(f[l][r][1], f[l][r - 1][0] + (pos[r] - pos[l]) * (sum[n] - sum[r - 1] + sum[l - 1]));
		}
	}
	cout << min(f[1][n][0], f[1][n][1]) << endl;
	return 0;
}

/*
f[l][r]将l~r珠子合并，后的最大值
f[l][r] = max(f[l][k]+f[k+1][r]+p[l].a*p[k].b*p[r].b)
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 205;
int n, f[N][N];

struct node {
	int a, b;
} p[N];
int a[N];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = n + 1; i <= n * 2; i++) {
		a[i] = a[i - n];
	}
	for (int i = 1; i <= 2 * n; i++) {
		p[i].a = a[i];
		p[i].b = a[i + 1];
	}
	for (int len = 2; len <= n; len++) {
		for (int l = 1; l + len - 1 <= 2 * n; l++) {
			int r = l + len - 1;
			for (int k = l; k < r; k++)
				f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + p[l].a * p[k].b * p[r].b);
		}
	}
	int res = 0;
	for (int i = 1; i <= n; i++) {
		res = max(res, f[i][i + n - 1]);
	}
	cout << res << endl;
	return 0;
}