/*
O(n ^ 3) solution
The order in which we remove elements matters. That's why we will cover all possible ways to
remove an element.In my solution dp[i][j] represents the answer when we removed elements
from i to j. dp[i][j] will be maximum of (dp[i][k - 1] + a[i - 1]*a[k]*a[j + 1] + dp[k + 1][j])
for k belonging to [i, j]. Basically we partition at different k, take the left and right
subarray and the contribution of element at kth index.
*/
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++) cin >> a[i];
vector<vector<int>> dp(n, vector<int>(n));
for(int i = n - 1; i >= 0; i--) {
for(int j = i; j < n; j++) {
// calculate dp[i][j]
for(int k = i; k <= j; k++) {
// we already remved [i, k - 1] and [k + 1, j]
int cur = (k - 1 >= i ? dp[i][k - 1] : 0) + (k + 1 <= j ? dp[k + 1][j] : 0);
int my = a[k] * (i > 0 ? a[i - 1] : 1) * (j + 1 < n ? a[j + 1] : 1);
dp[i][j] = max(dp[i][j], cur + my);
}
}
}
cout << dp[0][n - 1];
return 0;
}
LyogCk8obiBeIDMpIHNvbHV0aW9uClRoZSBvcmRlciBpbiB3aGljaCB3ZSByZW1vdmUgZWxlbWVudHMgbWF0dGVycy4gVGhhdCdzIHdoeSB3ZSB3aWxsIGNvdmVyIGFsbCBwb3NzaWJsZSB3YXlzIHRvIApyZW1vdmUgYW4gZWxlbWVudC5JbiBteSBzb2x1dGlvbiBkcFtpXVtqXSByZXByZXNlbnRzIHRoZSBhbnN3ZXIgd2hlbiB3ZSByZW1vdmVkIGVsZW1lbnRzIApmcm9tIGkgdG8gai4gZHBbaV1bal0gd2lsbCBiZSBtYXhpbXVtIG9mIChkcFtpXVtrIC0gMV0gKyBhW2kgLSAxXSphW2tdKmFbaiArIDFdICsgZHBbayArIDFdW2pdKSAKZm9yIGsgYmVsb25naW5nIHRvIFtpLCBqXS4gQmFzaWNhbGx5IHdlIHBhcnRpdGlvbiBhdCBkaWZmZXJlbnQgaywgdGFrZSB0aGUgbGVmdCBhbmQgcmlnaHQgCnN1YmFycmF5IGFuZCB0aGUgY29udHJpYnV0aW9uIG9mIGVsZW1lbnQgYXQga3RoIGluZGV4LgoqLwoKI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpCnsKICAgIGlvczo6c3luY193aXRoX3N0ZGlvKDApOwogICAgY2luLnRpZSgwKTsKICAgIAogICAgaW50IG47CiAgICBjaW4gPj4gbjsKICAgIHZlY3RvcjxpbnQ+IGEobik7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSBjaW4gPj4gYVtpXTsKICAgIAogICAgdmVjdG9yPHZlY3RvcjxpbnQ+PiBkcChuLCB2ZWN0b3I8aW50PihuKSk7CiAgICBmb3IoaW50IGkgPSBuIC0gMTsgaSA+PSAwOyBpLS0pIHsKICAgICAgICBmb3IoaW50IGogPSBpOyBqIDwgbjsgaisrKSB7CiAgICAgICAgICAgIAogICAgICAgICAgICAvLyBjYWxjdWxhdGUgZHBbaV1bal0KICAgICAgICAgICAgZm9yKGludCBrID0gaTsgayA8PSBqOyBrKyspIHsKICAgICAgICAgICAgICAgIC8vIHdlIGFscmVhZHkgcmVtdmVkIFtpLCBrIC0gMV0gYW5kIFtrICsgMSwgal0KICAgICAgICAgICAgICAgIGludCBjdXIgPSAoayAtIDEgPj0gaSA/IGRwW2ldW2sgLSAxXSA6IDApICsgKGsgKyAxIDw9IGogPyBkcFtrICsgMV1bal0gOiAwKTsKICAgICAgICAgICAgICAgIGludCBteSA9IGFba10gKiAoaSA+IDAgPyBhW2kgLSAxXSA6IDEpICogKGogKyAxIDwgbiA/IGFbaiArIDFdIDogMSk7CiAgICAgICAgICAgICAgICBkcFtpXVtqXSA9IG1heChkcFtpXVtqXSwgY3VyICsgbXkpOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQogICAgCiAgICBjb3V0IDw8IGRwWzBdW24gLSAxXTsKICAgIAogICAgcmV0dXJuIDA7Cn0=