#include<cstdio>

#include<cctype>

#include<algorithm>

inline long long max(long long a,long long b){    return a>b?a:b;    }

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        ch=getchar();

    }

    return num*f;

}

long long f[][];

int rt[][];

int que[];

void dfs(int x,int y){

    printf("%d ",rt[x][y]);

    if(rt[x][y]>x)    dfs(x,rt[x][y]-);

    if(rt[x][y]<y)    dfs(rt[x][y]+,y);

}

int main(){

    int n=read();

    for(int i=;i<=n;++i){

        f[i][i]=que[i]=read();

        rt[i][i]=i;

    }

    for(int l=;l<=n;++l)

        for(int i=;i+l-<=n;++i){

            int j=i+l-;

            for(int k=i;k<=j;++k){

                long long L=f[i][k-],R=f[k+][j];

                if(k==i&&k!=j)    L=;

                if(k==j&&k!=i)    R=;

                if(f[i][j]<L*R+f[k][k]){

                    rt[i][j]=k;

                    f[i][j]=L*R+f[k][k];

                }

            }

        }

    printf("%lld\n",f[][n]);

    dfs(,n);

    return ;

}