A full binary tree consists of a certain number of nodes. Each node has either two children, a left and a right one, or no children at all, in which case it is called a leaf. If node $v$ is a child of node $u$, then $u$ is called the parent of $v$. The root of the tree is the node that has no parent. In diagrams, the root is usually depicted at the top of the tree. For example, the figure below shows a full binary tree with 15 nodes and 8 leaves.

A subtree of a binary tree is any node along with all its descendants, i.e., its children, the children of its children, etc. Subtrees are called disjoint if they do not share any nodes. The depth of a node is the number of nodes on the path from the root to that node, excluding the root. Thus, for example, the tree in the figure above has leaves located at depths 3, 3, 3, 3, 2, 4, 4, 3, respectively. Note that by knowing the depths of the consecutive leaves, we can uniquely reconstruct the shape of the tree.

Description

Bajtazar is a computer scientist who works on data compression. Recently, he has been working on compression using binary prefix codes, which can be represented as full binary trees. If we use a certain prefix code for compression, the tree describing that code must also be included in the compressed file, so it is desirable for its description to be as small as possible.

Bajtazar has devised a method for compressing full binary trees. He chooses a number of disjoint subtrees, each of which has leaves at either one depth or two depths differing by 1, and replaces each of these subtrees with a leaf. Bajtazar compresses the tree in such a way that the resulting tree consists of the smallest possible number of nodes. For example, as a result of compressing the tree above, we obtain the following tree with five nodes:

From the perspective of prefix code efficiency, the exact appearance of its binary tree is not important, only the depths at which the leaves are located in that tree. We say that two trees are equivalent if they have the same multiset (i.e., a set with repetitions) of leaf depths. For example, the following full binary tree has leaves at the same depths as the previous one:

And as a result of its compression, we obtain a tree with only three nodes:

Bajtazar has a full binary tree $T$ describing a certain prefix code. He would now like to construct an equivalent tree $T'$ such that after compressing $T'$, the resulting number of nodes is minimized.

Input

The first line of the input contains a single integer $n$ ($1 \le n$), representing the number of leaves in the full binary tree $T$. The second line contains a sequence of $n$ non-negative integers $l_1, \dots, l_n$, separated by single spaces, representing the depths of the consecutive leaves (in order from left to right) in this tree.

Output

Your program should output two lines. The first line should contain a single integer representing the minimum number of nodes in the compressed tree obtained from some full binary tree $T'$ equivalent to tree $T$. The second line should contain the sequence of leaf depths of tree $T'$, in order from left to right. If there is more than one correct answer, your program should output any one of them.

Examples

Input 1

8
3 3 3 3 2 4 4 3

Output 1

3
2 3 3 3 3 3 4 4

Subtasks

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.

A program that outputs the correct result in the first line but an incorrect one in the second line will receive 50% of the points for the test. However, it is required that the second line contains the leaf depths from the input, in any order.