Height of a Binary Search Tree

Given a sequence of integers, construct a Binary Search Tree (BST) by inserting the values one by one. The height of the tree is defined as the maximum distance from the root to any leaf node, with the convention that an empty tree has a height of (-1). The BST insertion rule is: if the new value is less than the current node's value, insert it into the left subtree; otherwise, insert it into the right subtree.

Your task is to calculate the height of the BST after all insertions.

inputFormat

The input consists of two lines. The first line contains a single integer (n) ((n \ge 0)) representing the number of nodes. The second line contains (n) space-separated integers which are the values to be inserted into the BST. If (n = 0), the second line will be empty.

outputFormat

Output a single integer representing the height of the BST. Recall that the height is defined as the number of edges in the longest path from the root to a leaf, with an empty tree having a height of (-1) and a tree with only one node (the root) having a height of 0.## sample

9
5 3 8 1 4 7 10 2 9

3