Prevtree

Time limit2sMemory limit128 MB

Summary

Given the display code sequence (leaf-counts of root and left-children) of a strict binary tree, reconstruct the tree and output the lexicographically previous valid display code with the same leaf count, or 0 if none exists.

Level: Hard8 of 10
Topics: Tree, Recursion, Combinatorics, Greedy
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples1

Example 1
Input
```
5
5 4 1 1 1
```
Expected output
```
5 3 2 1 1
```