void solve() {
    int n;
    cin >> n;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) a.push_back(a[i]);

    n *= 2;
    vector<int> b(n + 1);
    for (int i = 1; i <= n; i++) {
        int sufi = i + 1;
        if (sufi == n + 1) sufi = 1;
        b[i] = a[sufi];
    }

    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
    for (int len = 2; len <= n / 2; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            for (int k = l; k < r; k++) {
                dp[l][r] = max(dp[l][r], dp[l][k] + dp[k + 1][r] + a[l] * b[r] * b[k]);
            }
        }
    }
    int res = 0;
    for (int l = 1; l <= n / 2; l++) {
        res = max(res, dp[l][l + n / 2 - 1]);
    }
    cout << res << '\n';
}