Unlike the other problems in this set, this tree is not built by inserting keys one at a time — it is built directly from a sorted array.
You are given n distinct integers, already sorted in strictly ascending order. Build a binary search tree from them using the standard recursive middle-element method: build(lo, hi) returns an empty tree when lo > hi; otherwise let mid = (lo + hi) // 2 (integer floor division), create a node holding a[mid], and attach build(lo, mid - 1) as its left child and build(mid + 1, hi) as its right child. The whole tree is build(0, n - 1).
Report the height of the resulting tree, where the height of an empty tree is 0 and the height of a tree with a single node is 1 (i.e., height is the number of nodes on the longest root-to-leaf path).
Input format
Line 1: an integer n.
Line 2: n space-separated integers a_1 < a_2 < ... < a_n, already sorted ascending.
Output format
A single integer: the height of the tree built by the method above.
Constraints
- 1 ≤ n ≤ 40
- -1000 ≤ each value ≤ 1000, strictly ascending