题目背景

原题来自 NOIP 2003。

题目描述

设一棵有 $n$ 个节点的二叉树的中序遍历为 $(1,2,3,\ldots,n)$，其中数字 $1,2,3,\ldots,n$ 为节点编号。每个节点都有一个正整数分数，第 $i$ 个节点的分数为 $d_i$。

这棵树以及它的每棵子树都有一个加分。设某棵子树的左子树加分为 $l$，右子树加分为 $r$，根节点分数为 $a$，则这棵子树的加分为：

如果某个子树为空，规定其加分为 $1$。叶子的加分就是该叶节点本身的分数。

请构造一棵符合中序遍历为 $(1,2,3,\ldots,n)$ 的二叉树，使整棵树的加分最高。

输入格式

第一行包含一个整数 $n$，表示节点个数。

第二行包含 $n$ 个正整数 $d_1,d_2,\ldots,d_n$，表示各节点的分数。

输出格式

第一行输出一个整数，表示最高加分。

第二行输出 $n$ 个整数，表示该树的前序遍历，相邻整数之间用一个空格分隔。

样例

5
5 7 1 2 10

145
3 1 2 4 5

来源

一本通 5.2 练习 1

数据范围与提示

• $n < 30$
• $d_i < 100$
• 结果不超过 $4 \times 10^9$