题目描述

原题来自：NOIP 2003

设一个$\red{ n }$个节点的二叉树 tree 的中序遍历为$\red{ (1,2,3,\cdots,n)}$，其中数字$\red{ 1,2,3,\cdots,n}$ 为节点编号。每个节点都有一个分数（均为正整数），记第 $\red{i }$个节点的分数为 $\red{d_i}$，tree 及它的每个子树都有一个加分，任一棵子树 subtree（也包含 tree 本身）的加分计算方法如下：

记 subtree 的左子树加分为 $\red{l}$，右子树加分为 $\red{r}$，subtree 的根的分数为 $\red{a}$，则 subtree 的加分为：

$\red{l\times r+a}$

若某个子树为空，规定其加分为$\red{ 1}$，叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为$\red{ (1,2,3,\cdots,n)}$ 且加分最高的二叉树 tree。

要求输出：

$\red{1}$. tree 的最高加分；

$\red{2}$. tree 的前序遍历。

输入格式

第一行一个整数$\red{ n }$表示节点个数；

第二行$\red{ n }$个空格隔开的整数，表示各节点的分数。

输出格式

第一行一个整数，为最高加分$\red{ b}$；

第二行$\red{ n}$ 个用空格隔开的整数，为该树的前序遍历。

样例

输入样例

5
5 7 1 2 10

输出样例

145
3 1 2 4 5

提示

对于$\red{ 100\%}$ 的数据，$\red{n\lt 30,b\lt 100}$，结果不超过 $\red{4\times 10^9}$。