Prevtree

A strict binary tree is a binary tree in which every non-leaf node has exactly two children. The leaf value of a node is the number of leaf nodes in the subtree rooted at that node.

The following tree is a strict binary tree. Each number shown at a node is that node's leaf value.

      *7              / \            /   \          /     \       *4       3      / \     / \   *1   3  *1   2      / \     / \   *2   1  *1   1  / \           *1   1          

During a preorder traversal of such a tree, list the leaf values of the root and of every node that is a left child. For the tree above, the marked nodes are listed, producing (7, 4, 1, 2, 1, 1, 1). This sequence is called the display code of the tree.

Given the display code of a strict binary tree, find the display code that comes immediately before it in lexicographic order among trees with the same number of leaf nodes.

The first line contains the length L of the display code, where 1 <= L <= 10,000.

The second line contains L integers separated by spaces, representing the display code.

If the given display code is the first one in lexicographic order, print 0.

Otherwise, print the display code that comes immediately before the given code in lexicographic order.