Maximum Bonus Binary Tree

You are given a binary tree with n nodes numbered 1,2,...,n such that its inorder traversal is exactly (1,2,3,...,n). Each node i has an associated positive integer score d_i.

For any non‐empty subtree (including the entire tree), its bonus is defined as follows:

bonus(subtree) = {\(\text{(bonus(left_subtree))} \times \text{(bonus(right_subtree))} + d_{root}\)}

However, if a subtree is empty, we define its bonus as \(1\). In addition, if a node is a leaf (i.e. both of its children are empty), then its bonus is defined to be its own score d_i (and not \(1 \times 1 + d_i\)).

Your task is to construct a binary tree satisfying the above inorder order that achieves the maximum bonus for the entire tree. You need to output the maximum bonus and also the preorder traversal of the corresponding tree.

Note: If a subtree has only one non‐empty branch, then use the bonus from that branch (and use 1 for the missing subtree) in the formula.

inputFormat

The input consists of two lines. The first line contains a single integer n (1 ≤ n ≤ 1000) representing the number of nodes. The second line contains n positive integers d₁, d₂, ..., d_n separated by spaces, where d_i is the score of node i in the inorder traversal order.

outputFormat

Output two lines. The first line should contain the maximum bonus of the tree. The second line should contain the preorder traversal of the tree (i.e. the node numbers separated by spaces) corresponding to the tree with the maximum bonus.

sample

1
5

5
1