#include<bits/stdc++.h>
using namespace std;
int n, f[30][30], root[30][30], score = 0;

void print(long long l, long long r)//输出前序遍历
{
	if (l > r)
		return;
	cout << root[l][r]<<" ";//从最大的树的根开始输出，因为前序遍历是(根->左->右)
	if (l == r)
		return;
	print(l, root[l][r] - 1);//分治左子树
	print(root[l][r] + 1, r);//分治右子树
}
int main()
{
	cin >> n;//节点数
	for (int i = 1; i <= n; i++)
	{
		cin >> f[i][i];//输入当前节点分值
		root[i][i] = i;//初始化root(只有一个i节点的子树的根节点就是自己啊)
	}
	for (int len = 1; len < n; ++len)//子树的长度（节点数）
	{
		for (int i = 1; i + len <= n; i++)//间接改变j的值（即树的大小），也定下了区间右侧的值
		{
			int j = i + len;//定义树的最右边的节点，也就是区间左侧
			f[i][j] = f[i + 1][j] + f[i][i];//默认左子树为空，即根节点为i
			root[i][j] = i;//i~j的树的根为i
			for (int k = i + 1; k <= j; ++k)//枚举根节点，当子树中根的位置改变时分值也会变
			{
				if (f[i][j] < f[i][k - 1] * f[k + 1][j] + f[k][k])//以k为根时子树的分值
				{
					f[i][j] = f[i][k - 1] * f[k + 1][j] + f[k][k];//根据题意取最大值
					root[i][j] = k;//更新i~j的子树的根节点
				}
			}
		}
	}
	cout << f[1][n] << endl;//输出以k为根节点的整个树的分数
	print(1, n);//输出前序遍历
	return 0;
}