#include<cstdio>
using namespace std;
int n;
int a[6000];
long long dp[600][600];
struct ss
{int tou,wei;
}data[6000];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<n;i++)
{
data[i].tou=a[i];
data[i].wei=a[i+1];
}
data[n].tou=a[n];
data[n].wei=a[1];
data[0].tou=data[n].tou;
data[0].wei=data[n].wei;
data[n+1].tou=data[1].tou;
data[n+1].wei=data[1].wei;
for(int i=n;i>=0;i--)
for(int j=i+1;j<=n+1;j++)
{
for(int k=i;k<j;k++)
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+data[i].tou*data[k].wei*data[j].wei);
}
cout<<max(dp[0][n-1],max(dp[2][n+1],dp[1][n]));
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int f[405][405];
int n,a[205];
int main()
{
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i];
a[n+i]=a[i];
}
for(int i=2;i<=n+1;i++)
{
for(int l=1;l+i-1<=2*n;l++)
{
int r=l+i-1;
for(int k=l+1;k<=l+i-2;k++)
f[l][r]=max(f[l][r],f[l][k]+f[k][r]+a[l]*a[k]*a[r]);
}
}
int res=0;
for (int i=1;i<=n;i++) res=max(res,f[i][n+i]);
cout << res;
return 0;
}
#include<cstdio>
#include<algorithm>
#pragma GCC optimize(2)
using namespace std;
const int mx=110;
int n,ans=0;
int a[mx*2],f[mx*2][mx*2];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i+n]=a[i];
for(int i=2;i<=n+1;i++){
for(int l=1;l+i-1<=n*2;l++){
int r=l+i-1;
for(int k=l+1;k<=l+i-2;k++){
f[l][r]=max(f[l][r],f[l][k]+f[k][r]+a[l]*a[k]*a[r]);
}
}
}
for(int i=1;i<=n;i++)ans=max(ans,f[i][n+i]);
printf("%d",ans);
return 0;
}
#include<algorithm>
#pragma GCC optimize(2)
using namespace std;
const int mx=110;
int n,ans=0;
int a[mx*2],f[mx*2][mx*2];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i+n]=a[i];
for(int i=2;i<=n+1;i++){
for(int l=1;l+i-1<=n*2;l++){
int r=l+i-1;
for(int k=l+1;k<=l+i-2;k++){
f[l][r]=max(f[l][r],f[l][k]+f[k][r]+a[l]*a[k]*a[r]);
}
}
}
for(int i=1;i<=n;i++)ans=max(ans,f[i][n+i]);
printf("%d",ans);
return 0;
}