插入后的叶节点数

难度：T2

【知识点：二叉搜索树】

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

题目描述

从空的二叉搜索树开始，按给定次序插入关键字，重复值忽略。全部操作完成后，统计左右孩子都不存在的节点数，即叶节点数。

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

输入格式

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

输出格式

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

样例输入

7
40 20 70 10 30 60 90

样例输出

4

样例解释

叶节点是$10$、$30$、$60$、$90$，共$4$个。

数据范围

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