题目描述

设一个n个节点的二叉树$\mathrm{tree}$的中序遍历为$(1,2,3, \cdots,n)$，其中数字$1,2,3, \cdots,n$为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为$d_i$，$\mathrm{tree}$及它的每个子树都有一个加分，任一棵子树$\mathrm{subtree}$（也包含$\mathrm{tree}$本身）的加分计算方法如下： 记$\mathrm{subtree}$的左子树加分为l，右子树加分为r，$\mathrm{subtree}$的根的分数为a，则$\mathrm{subtree}$的加分为： $l \times r+a$ 若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为$(1,2,3, \cdots,n)$且加分最高的二叉树$\mathrm{tree}$。 要求输出： $\mathrm{tree}$的最高加分；$\mathrm{tree}$的前序遍历。输入格式

1. 第一行一个整数n表示节点个数；- 第二行n个空格隔开的整数，表示各节点的分数。

输入描述

第一行一个整数n，表示节点个数； 第二行n个用空格隔开的整数，表示di。

输出描述

第一行一个整数，为最高加分b； 第二行n个用空格隔开的整数，为该树的前序遍历。

示例1

输入

5
5 7 1 2 10

输出

145
3 1 2 4 5

备注

数据范围

对于$100 \%$的数据，$n \lt30,d_i \lt100$，结果不超过$4 \times10^9$。