AC

#include <bits/stdc++.h>

using namespace std;

int main() {

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

vector<vector<unsigned long long>> dp(n + 2, vector<unsigned long long>(n + 2, 1));
vector<vector<int>> root(n + 2, vector<int>(n + 2, 0));

for (int i = 1; i <= n; ++i) {
    dp[i][i] = scores[i];
    root[i][i] = i;
}

for (int len = 2; len <= n; ++len) {
    for (int i = 1; i <= n - len + 1; ++i) {
        int j = i + len - 1;
        for (int k = i; k <= j; ++k) {
            unsigned long left = (k == i) ? 1 : dp[i][k - 1];
            unsigned long right = (k == j) ? 1 : dp[k + 1][j];
            unsigned long value = left * right + scores[k];
            if (value > dp[i][j]) {
                dp[i][j] = value;
                root[i][j] = k;
            }
        }
    }
}

cout << dp[1][n] << endl;

vector<int> preorder;
function<void(int, int)> build_preorder = [&](int l, int r) {
    if (l > r) return;
    int k = root[l][r];
    preorder.push_back(k);
    build_preorder(l, k - 1);
    build_preorder(k + 1, r);
};

build_preorder(1, n);
for (int i = 0; i < preorder.size(); ++i) {
    if (i > 0) cout << " ";
    cout << preorder[i];
}
cout << endl;

return 0;

}