Height of a BST

Medium#trees #binary-search-tree· solved by 0 · time limit 2.0 s

Insert distinct values one by one into an empty binary search tree (smaller values go left, larger go right). Print the tree's height — the number of nodes on the longest root-to-leaf path.

Input

$n$ , then the $n$ distinct values in insertion order.

Output

The height.

Constraints

$1 \le n \le 2000$

Sample 1

Input

5
50 30 70 20 40

Output

Sample 2

Input

3
1 2 3

Output