A dispatcher inserts distinct integer priorities into a binary search tree, one at a time, in the order given (standard BST insertion: go left when the new priority is smaller than the current node, otherwise go right). The insertion order fully determines the tree's shape. Report the height of the resulting tree, measured as the number of edges on the longest path from the root down to a leaf. A tree with a single node has height 0.
Input format
Line 1: an integer n, the number of priorities.
Line 2: n space-separated distinct integers, the priorities in insertion order.
Output format
A single integer: the height of the constructed BST, in edges.
Constraints
- 1 <= n <= 40
- All priorities are distinct, each with absolute value <= 1000000.