P2171 Hz 吐泡泡
题目背景
Hz 大大是一种可爱的动物(神)。他很喜欢吐泡泡(更喜欢写作业)。
题目描述
这天,Hz 大大心血来潮,吐了 $n$ 个不同的泡泡玩(保证没有重复的泡泡)。因为他还要写作业,所以他请你帮他把这些泡泡排序成树。输出它的后序遍历。
具体来说,Hz 会使用二叉查找树(BST)的算法,将这些泡泡**依次**插入到树中。每次插入后新的泡泡位于一个叶子上,并且整棵树的中序遍历保持升序。
全部插入完成后的二叉树即是所要求的树。
输入格式
共 $2$ 行。
第一行,$1$ 个整数 $n$。
第二行,$n$ 个整数,第 $i$ 个整数 $a_i$ 代表第 $i$ 个泡泡的大小。
输出格式
共 $2$ 行。
第一行,输出树的深度。
接下来输出 n 行,一行一个整数,表示树的后序遍历。
说明/提示
本题分为两个 Subtask,第一个 Subtask 共 10 个测试点,每个测试点 5 分,第二个 Subtask 共 5 个测试点,每个测试点 10 分。
$1\le n\le 3\times 10^5$,$1\le a_i\le 10^9$,所有 $a_i$ 互不相同。