题目描述

输入一系列整数，利用所给数据建立一个二叉搜索树，并输出其前序、中序和后序遍历序列。

输入格式

第一行包含一个整数 $n$，表示输入整数数量。

第二行包含 $n$ 个整数。

输出格式

输出共三行，第一行输出前序遍历序列，第二行输出中序遍历序列，第三行输出后序遍历序列。

输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。

样例

5
1 6 5 9 8

1 6 5 9 8
1 5 6 8 9
5 8 9 6 1

样例分析

如上所述。

数据范围与提示

• 对于 $100\%$ 的数据，$1 \le n \le 100$。
• 输入元素取值范围为 $[1,1000]$。