Description

Let a binary tree $\text{tree}$ with $n$ nodes have an inorder traversal of $(1, 2, 3, \ldots, n)$, where $1, 2, 3, \ldots, n$ are the node indices. Each node has a positive integer score; denote the score of node $i$ as $d_i$. The tree and each of its subtrees have a score. For any subtree $\text{subtree}$ (including $\text{tree}$ itself), its score is computed as follows:

score of the left subtree of $\text{subtree}$ $\times$ score of the right subtree of $\text{subtree}$ $+$ score of the root of $\text{subtree}$.

If a subtree is empty, its score is defined as $1$. The score of a leaf equals the score of the leaf node itself; its empty children are not considered.

Find a binary tree $\text{tree}$ whose inorder traversal is $(1, 2, 3, \ldots, n)$ and whose score is maximized. Output:

1. The maximum score of $\text{tree}$.
2. The preorder traversal of $\text{tree}$.

Input Format

The first line contains one integer $n$, the number of nodes.

The second line contains $n$ space-separated integers, the score of each node.

Output Format

The first line contains one integer, the maximum score ($Ans \le 4,000,000,000$).

The second line contains $n$ space-separated integers, the preorder traversal of the tree.

5
5 7 1 2 10

145
3 1 2 4 5

Hint

Constraints

For all testdata, it is guaranteed that $1 \le n < 30$, each node’s score is a positive integer less than $100$, and the answer does not exceed $4 \times 10^9$.

Translated by ChatGPT 5