Next Binary Tree Encoding

Farmer John's farm contains many apple trees, each of which is a binary tree (although not strictly complete – a node might have only a left child or only a right child). In these trees every internal node (i.e. a node that is not a leaf) is recorded with the number of nodes in its left subtree. The tree is then encoded by a preorder traversal that outputs the value at each internal node (leaf nodes are omitted). Moreover, the total number of nodes in the tree is written as the first number of the encoding.

For example, consider the binary tree below:

                3
              /   \
             1     3
            / \   / \
           0   0  1   0
                 / \
                0   0

Its encoding is:

9 3 1 3 1

Unique Decoding: All trees on the farm have the same total number of nodes, and for any valid encoding with that fixed total there is a unique corresponding binary tree.

Besty the cow sorts all the valid encodings lexicographically (comparing the sequence element‐by‐element, noting the first number is always the same). Given one such encoding, your task is to compute the lexicographically next valid encoding.

When one internal node’s recorded value (the number of nodes in its left subtree) is increased (provided it does not exceed its maximum allowed value, which is the total nodes in that subtree minus one), the subtree below that node must be replaced with its lexicographically smallest valid encoding. This minimal encoding for any subtree is obtained by, at every internal node, choosing 0 (which corresponds to having only a right child) wherever possible. Formally, if a subtree has x nodes then:

• If x = 1, the subtree is just a leaf and its encoding is empty.
• If x > 1, then its minimal encoding is: [0] concatenated with the minimal encoding for a subtree of x-1 nodes.

Your task is to find, among all valid encodings (with fixed total nodes), the one which comes immediately after the input encoding in lexicographical order.

inputFormat

The input consists of a single line containing several integers separated by spaces. The first integer is the total number of nodes in the binary tree. The remaining integers represent the preorder encoding of the tree (only the internal nodes are encoded). You may assume that the input encoding is valid and that a lexicographically larger encoding exists.

outputFormat

Output a single line containing the next lexicographically larger valid encoding. Output the sequence of integers (the total node count followed by the encoding) separated by single spaces.

sample

9 3 1 3 1

9 3 1 3 2 0