Count the Leaf Nodes in a Binary Search Tree

You are given a sequence of integers that are inserted into a Binary Search Tree (BST) in the given order. Your task is to construct the BST and count the number of leaf nodes.

A leaf node is defined as a node that does not have any children. In other words, if a node n has no left child and no right child, then it is a leaf node. Mathematically, a node n is a leaf if:

$$\text{if } n.left = \text{null and } n.right = \text{null}$$

Please note that all input integers are distinct.

inputFormat

The first line contains an integer n, representing the number of nodes to be inserted into the BST. The second line contains n space-separated integers representing the insertion sequence.

Example:

7
10 5 1 7 40 50 30

outputFormat

Output a single integer representing the number of leaf nodes in the BST.

Example:

4

## sample

7
10 5 1 7 40 50 30

4