309 - 二叉搜索树

通过次数

2

提交次数

2

时间限制 : 1 秒
内存限制 : 128 MB

按照二叉搜索树的规则建树。

二叉搜索树:它或者是一棵空树,或者是具有下列性质的二叉树:

1、若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;

2、若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;

3、它的左、右子树也分别为二叉搜索树。

输入

第一行输入一个整数n,表示数的节点个数。

第二行输入与n个不同的数字,按节点出现的顺序给出。

输出

输出共n行,第i行输出第i个插入的数的左右儿子的插入编号,插入编号从1开始计数。

样例

输入

6
3 2 4 7 5 1

输出

1: 2 3
2: 6 #
3: # 4
4: 5 #
5: # #
6: # #

提示

15851961433044.png

数据规模

1≤n≤10000,数字大小在int范围内。