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

1
5

1

7
1 2 3 4 5 6 7

3