## Interval DP: Bonus Binary Tree

Design an in-order traversal of a binary tree. Nodes are numbers (1 , 2 , 3 , … , n), where the number 1 , 2 , 3 , … , n is the node id. Each node has a score (positive integer) and each subtree has a bonus. The subtree bonus calculation is based on bonus of its subtrees and the score of the node itself:       bonus for the left subtree * bonus for the right subtree + the score of the root of the subtree

If a subtree is empty, then the bonus is 1, all the leaf nodes’ bonus is the score of the leaf node.

Try to find a tree that gives an in-order traversal as (1 , 2 , 3 , … , n) and the binary tree with the highest bonus.

Request output:

(1) The highest points for tree  (2) Preorder traversal of tree

Input format First row: an integer n, Is the number of nodes.  Second row: an integer separated by a space is the score of each node (0 <fraction< 100).

Output format First row: an integer, which is the highest bonus point (the result will not exceed the intrange).      Second row: an integer separated by a space which is the print out of pre-order traversal of the tree. If there are multiple schemes, the scheme with the smallest lexicographic order is output.

data range n < 30

Sample Input:

5
5 7 1 2 10


Sample Output:

145
3 1 2 4 5