dp
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int f[35][35];//存放i到j的分数
int g[35][35];//存放i到j的根
int w[35];
void dfs(int x,int n){
if(x>n) return;
cout<<g[x][n]<<' ';
dfs(x,g[x][n]-1);dfs(g[x][n]+1,n);
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>w[i];
}
for(int len=1;len<=n;len++){//枚举长度,区间长度
for(int i=1;i+len-1<=n;i++){//i+len-1等于右侧端点值,i为左区间的值
int j=i+len-1;
if(len==1){
f[i][j]=w[i];
g[i][j]=i;
}
else {
for(int k=i;k<=j;k++){
int left=k==i?1:f[i][k-1];
int right=k==j?1:f[k+1][j];
int sc=left*right+w[k];
if(sc>f[i][j]){
f[i][j]=sc;//更新分数
g[i][j]=k;//更新根节点
}
}
}
}
}
cout<<f[1][n]<<endl;
dfs(1,n);
return 0;
}