全部书号各查一次

难度：T2

【知识点：二叉搜索树】

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

题目描述

从空的二叉搜索树开始，按给定次序插入关键字，重复值忽略。对最终存在的每个不同关键字，各从根成功查找一次，求所有查找访问的真实节点总数。根计入，空孩子不计入，重复输入的关键字只查一次。

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

输入格式

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

输出格式

一行一个整数，空树输出 $0$。

样例输入

7
40 20 70 10 30 60 90

样例输出

17

样例解释

根访问$1$次，深度$1$的两个节点各$2$次，深度$2$的四个节点各$3$次，总共$17$次。

数据范围

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