按登记顺序建立索引

难度：T2

【知识点：二叉搜索树】

前置：一维数组、循环、函数、树与遍历

题目描述

从空的二叉搜索树开始，按给定次序依次插入登记的关键字；已存在的值忽略。最后按先序，即根、左子树、右子树输出关键字。不要先排序再插入。

本题BST的每个节点，其左子树全部关键字更小，右子树全部关键字更大。关键字可为负数或 $0$。

输入格式

第一行一个整数 $n$，表示登记次数。第二行按次序给出 $n$ 个整数，表示要插入的关键字；$n=0$ 时没有第二行。空树首次插入创建根；非空时相等忽略，小向左、大向右，最终接到第一个空孩子处。

输出格式

一行先序关键字序列，空格分隔；空树输出 EMPTY。

样例输入

7
40 20 70 10 30 60 90

样例输出

40 20 10 30 70 60 90

样例解释

$40$为根，左子树先序$20$、$10$、$30$，右子树先序$70$、$60$、$90$。

数据范围

$0\le n\le200$，所有关键字在 $-1000$ 到 $1000$ 之间。