/* 
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=

NQozIDUgMSA4IDI=

5
3 5 1 8 2