索引树有多高

难度：T2

【知识点：二叉搜索树】

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

题目描述

从空的二叉搜索树开始，按给定次序插入关键字，重复值忽略。求最后树的高度：高度是根到最深节点经过的边数，单节点高度为 $0$，空树输出 $-1$。

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

输入格式

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

输出格式

一行一个整数，表示按边数计算的树高。

样例输入

7
40 20 70 10 30 60 90

样例输出

2

样例解释

根到最深节点经过$2$条边。

数据范围

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