A. 在树上签到

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

现在,给出一个树的中序遍历,输入元素的序号依次为1~N,输入元素为该节点的分数,求在AK规则下分支最高的树。

AK规则

  1. 如果一个节点是叶子节点,那么该节点为根的树的分数为该节点自身的分数。

  2. 如果一个节点有有子树,那么该节点为根的树的分数为左子树分数 右子树分数 + 该节点分数。

  3. 如果某个子树为空,则为空的子树分数视为1。

输入格式

第一行,一个正整数N,表示节点个数。

第二行,N个正整数,表示序号为1~N的节点的分数,输入顺序(1~N)即为中序遍历顺序。

输出格式

第一行,一个正整数,表示该树的分数。

第二行,N个正整数,表示该树前序遍历时,各个节点的序号,保证前序遍历唯一。

样例

输入样例

5
5 7 1 2 10

输出样例

145
3 1 2 4 5

数据范围与提示

,所有过程量及答案不超过9

提示可以看分类标签。

通告标题

通告内容

已知晓