9199 - 下一棵树

农场有n(1<=n<=1000)棵树,在上过“数据结构”课程后,小Y发现所有的树实际上都是严格二叉树,二叉树的每个非叶结点都恰好有两个子结点,小Y给每个结点一个数来表示以这个结点为根的子树的叶结点数,然后,小Y按照先序遍历思想把和结点相关的数列出作为它的特征序列。但是,他只列出了与根结点和所有的左子结点相关的数。例如对下图所示的树,用*表示的是小Y列出的结点,这棵树的特征序列为:(7 4 1 2 1 1 1)。在用这种方法表示完所有的树后,小Y发现:(1)所有的树有同样多的结点;(2)所有的树有不同的特征序列;(3)所有可能的严格二叉树都在农场里。所以,小Y决定把这些特征序列排序,然后希望给出一棵树的特征序列,求出紧接着的一棵树的特征序列。

167956397194.png

输入

输入共两行,第一行为n的值,表示特征序列的长度;

第二行为n个用空格隔开的数,表示一棵树的特征序列。

输出

输出只有一行,表示按字典顺序排序后所给序列的后一个序列。如果所给序列是最后一个序列则输出0。记住:输入和输出序列代表的树要有相同的叶结点数。

样例

输入

5
5 3 2 1 1

输出

5 4 1 1 1
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题