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], i

    max_val = -1
    root = -1
    for 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, k

    return max_val, root

print(dp(0, N-1)[0])

# 先序遍历打印二叉树， 因为最优划分已经全部算出来了，所以现在一个区间的最优划分方案就对应一个子树的根
arr = []
def dfs(i, j):
    if j < i:
        return

    if i == j:
        arr.append(str(j+1))
        return

    root = dp(i, j)[1]
    arr.append(str(root+1))
    dfs(i, root-1)
    dfs(root+1, j)

dfs(0, N-1)
print(' '.join(arr))