题目描述

输入一列整数（允许重复），请你按顺序插入并创建二叉搜索树，之后输出中序和后序遍历序列（重复值也要输出）。

输入格式

2行。第1行一个整数n。第2行，n个空格隔开的整数（允许重复）。

输出格式

2行。中序和后序序列各一行。

样例

输入样例 1

7
14 3 5 7 1 20 8

输出样例 1

1 3 5 7 8 14 20
1 8 7 5 3 20 14

输入样例 2

10
14 3 3 5 7 1 3 20 8 20

输出样例 2

1 3 3 3 5 7 8 14 20 20
1 8 7 5 3 3 3 20 20 14

输入样例 3

20
-1 3 -11 20 131 11 29 -30 -100 7 17 56 245 121 -120 -12 120 111 0 200

输出样例 3

-120 -100 -30 -12 -11 -1 0 3 7 11 17 20 29 56 111 120 121 131 200 245
-120 -100 -12 -30 -11 0 7 17 11 111 120 121 56 29 200 245 131 20 3 -1