#include <bits/stdc++.h> 
using namespace std;
int f[31][31], root[31][31];
//动态规划的核心是理解好数据结构的表示意义
//f[i][j]表示如果第i个节点至第j个节点的所有点成为一个树，那么最大得分是多少
//root[i][j] 表示如果第i个节点至第j个节点的所有点成为一个树，那么根节点是谁 
int d[31];
void pre_dfs(int l, int r)//  对 从l到r的所有点 进行 先序遍历
{
    if(l <= r)
    {
        printf(" %d", root[l][r]);                     //先写中间
        pre_dfs(l, root[l][r]-1);//  对左子树先序遍历
        pre_dfs(root[l][r]+1, r);//  对右子树先序遍历
    }
}
 
int main()
{
    int n; scanf("%d", &n);
    for(int i=0; i <= n; i++)for(int j=0; j <= n; j++) f[i][j] = 1;//一般初始化都为0，为什么这里为1
    for(int i=1; i <= n; i++)
    {
        scanf("%d", &d[i]);
        root[i][i] = i;//一开始假设每个点最不济的情况就是叶子节点，那么它就是自己这个范围[i,i]的树的根（只有一个点） 
        f[i][i] = d[i];//一开始，每个点的加分只有自己的分值 
    }
    for(int k=2; k <= n; k++) // 枚举形式不唯一，但我喜欢从规模小打规模大
        for(int L=1; L <= n-k+1; L++)// 确定了长度为k，那么枚举开头L
        {
            int R = L + k - 1; //左边开始端点是L，长度为k，那么右边就是 L+k-1 
            for(int mid = L; mid <= R; mid++)// 枚举中间点 mid，mid就是 i到j所有点的根
            {
                if(f[L][R] < f[L][mid-1] * f[mid+1][R] + d[mid])
                {
                    f[L][R] = f[L][mid-1] * f[mid+1][R] + d[mid];//既然可以更新，那就是比以前的好，那么要及时记录
                    root[L][R] = mid;  //记录L到R这一段此刻之所以变得更大，是因为选中了mid作为这些点的根 
                }
            }
        }
    printf("%d\n", f[1][n]);
    //下面开始打印先序遍历的结果了 
    printf("%d", root[1][n]);
    pre_dfs(1, root[1][n]-1);
    pre_dfs(root[1][n]+1, n); 
    return 0;
}

#include<bits/stdc++.h> 
using namespace std;
int f[31][31],root[31][31];
//动态规划的核心是理解好数据结构的表示意义
//f[i][j]表示如果第i个节点至第j个节点的所有点成为一个树，那么最大得分是多少
//root[i][j] 表示如果第i个节点至第j个节点的所有点成为一个树，那么根节点是谁 
int d[31];
void pre_dfs(int l,int r)//  对 从l到r的所有点 进行 先序遍历
{
    if(l<=r)
    {
        printf(" %d",root[l][r]);                     //先写中间
        pre_dfs(      l         ,   root[l][r]-1    );//  对左子树先序遍历
        pre_dfs( root[l][r]+1   ,        r          );//  对右子树先序遍历
    }
}
 
int main()
{
    int n; scanf("%d",&n);
    for(int i=0;i<=n;i++)for(int j=0;j<=n;j++) f[i][j]=1;//一般初始化都为0，为什么这里为1
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&d[i]);
        root[i][i]=i;//一开始假设每个点最不济的情况就是叶子节点，那么它就是自己这个范围[i,i]的树的根（只有一个点） 
        f[i][i]=d[i];//一开始，每个点的加分只有自己的分值 
    }
    for(int k=2;k<=n;k++) // 枚举形式不唯一，但我喜欢从规模小打规模大
        for(int L=1;L<=n-k+1;L++)// 确定了长度为k，那么枚举开头L
        {
            int R=L+k-1; //左边开始端点是L，长度为k，那么右边就是 L+k-1 
            for(int mid=L;mid<=R;mid++)// 枚举中间点 mid, mid就是 i到j所有点的根
            {
                if( f[L][R] < f[L][mid-1] * f[mid+1][R] +d[mid] )
                {
                    f[L][R] = f[L][mid-1] * f[mid+1][R] +d[mid];//既然可以更新，那就是比以前的好，那么要及时记录
                    root[L][R]=mid;  //记录L到R这一段此刻之所以变得更大，是因为选中了mid作为这些点的根 
                }
            }
        }
    printf("%d\n",f[1][n]);
    //下面开始打印先序遍历的结果了 
    printf("%d",root[1][n]);
    pre_dfs(1,root[1][n]-1);
    pre_dfs(root[1][n]+1,n); 
    return 0;
}