Description

Original source: NOIP 2003

Given a binary tree tree with n nodes, its in-order traversal is (1,2,3,…,n), where the numbers 1,2,3,…,n represent the node identifiers. Each node has a score (all positive integers), with the score of the i-th node denoted as d_i. tree and each of its subtrees have a calculated score. The score of any subtree subtree (including tree itself) is computed as follows:

Let the score of the left subtree of subtree be l, the score of the right subtree be r, and the score of the root of subtree be a. Then, the score of subtree is:

If a subtree is empty, its score is defined as 1. The score of a leaf node is the score of the node itself, without considering its empty subtrees.

Your task is to find a binary tree tree that conforms to the in-order traversal (1,2,3,…,n) and has the highest possible score.

You are required to output:

1. The highest score b of tree;
2. The pre-order traversal of tree.

Input Format

The first line contains an integer n representing the number of nodes;

The second line contains n space-separated integers, representing the scores of each node.

Output Format

The first line should contain an integer, the highest score b;

The second line should contain n space-separated integers, representing the pre-order traversal of the tree.

Sample 1

5
5 7 1 2 10

145
3 1 2 4 5

Data Range and Hint

For 100% of the data, n < 30, b < 100, and the result does not exceed 4 × 10^9.