题目描述

二叉查找树又称二叉搜索树，树中每个结点最多有两个儿子，树上每个结点都有自己的数值，设 $key[p]$ 表示结点 $p$ 上的数值。二叉查找树具有这样的性质：对于其中的每个结点 $p$，若其存在左孩子 $lch$，则有 $key[lch] < key[p]$；若其存在右孩子 $rch$，则有 $key[p] < key[rch]$。

由于二叉查找树有许多特殊的性质，因此我们常常需要把一个普通的数组建成一棵二叉查找树，以完成各种特殊的操作。

通常我们使用插入法来构建二叉查找树，一开始是一个空树，插入的第一个数就设为树的根节点。

在非空的二叉查找树中插入一个数 $x$ 时，我们通常使用递归的方法插入。首先从根节点 $u$ 开始，把 $x$ 插入到以 $u$ 为根的子树上时，如果当前数 $x$ 比 $key[u]$ 小，则继续将 $x$ 插入到 $u$ 的左子树；否则将 $x$ 插入到 $u$ 的右子树；重复上述步骤，直到当前子树为空时，把 $x$ 插入到当前位置。

可以发现，即使是同样的数字，由于插入顺序不同，形成的二叉查找树的形态也会发生变化。现在给定一个数组，请你求出按照该顺序形成的二叉查找树的中序遍历和后序遍历。

输入格式

第一行一个正整数 $n$，表示插入次数，初始二叉树为空树。

第二行 $n$ 个正整数，用空格分隔，表示每次插入的数字的值，保证输入数据各不相同。

输出格式

第一行 $n$ 个用空格分隔的正整数，表示形成的二叉查找树的中序遍历。

第二行 $n$ 个用空格分隔的正整数，表示形成的二叉查找树的后序遍历。

输入样例 #1

5
3 1 4 2 5

输出样例 #1

1 2 3 4 5
2 1 5 4 3

输入样例 #2

7
10 2 5 6 7 8 9

输出样例 #2

2 5 6 7 8 9 10
9 8 7 6 5 2 10

输入样例 #3

7
6 7 10 8 2 5 9

输出样例 #3

2 5 6 7 8 9 10
5 2 9 8 10 7 6

数据范围

• 对于 $20\%$ 的数据，$N\le 20$；
• 对于 $50\%$ 的数据，$N\le 10000$；
• 对于全部的数据，$N\le 10^5$。输入的所有数字不大于 $10^9$。数据为随机构造。