N = int(input())
arr = list(map(int, input().split()))from functools import lru_cache# dp(i, j) 表示所有中序序列是arr[i:j+1]的二叉树的价值的最大值以及最大值对应的树的根节点
# 为了让前序序列的字典序最小，价值一样大情况下，根节点选更靠前的
@lru_cache(typed=False, maxsize=128000000)
def dp(i, j):if j == i:return arr[i], imax_val = -1root = -1for k in range(i, j + 1):if k == i:val = dp(i + 1, j)[0] + arr[i]elif k == j:val = dp(i, j - 1)[0] + arr[j]else:val = dp(i, k - 1)[0] * dp(k + 1, j)[0] + arr[k]if val > max_val:max_val, root = val, kreturn max_val, rootprint(dp(0, N - 1)[0])# 先序遍历打印二叉树， 因为最优划分已经全部算出来了，所以现在一个区间的最优划分方案就对应一个子树的根
arr = []def dfs(i, j):if j < i:returnif i == j:arr.append(str(j + 1))returnroot = dp(i, j)[1]arr.append(str(root + 1))dfs(i, root - 1)dfs(root + 1, j)dfs(0, N - 1)
print(' '.join(arr))