BST Height and Degeneration

Source: Phuoc Hung OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Build a BST from $a_1,a_2,\ldots,a_n$ in insertion order. Duplicate keys are ignored.

The root has depth $0$. The depth of any other node is the number of edges on the unique path from the root to that node. The height of a non-empty tree is the maximum node depth, equivalently the number of edges on a longest path from the root to a leaf.

By convention in this task, an empty tree has height $-1$.

Compute the height after all insertions.

Input

The first line contains $n$.

If $n>0$, the next line contains $n$ signed integers $a_1,a_2,\ldots,a_n$. If $n=0$, this line is absent.

Output

Print one integer: the height of the tree.

Subtasks

Subtask 1 (20 points): $0\le n\le 20$.

Subtask 2 (30 points): $0\le n\le 5000$.

Subtask 3 (50 points): $0\le n\le 200000$.

In all subtasks, $-2^{63}\le a_i\le 2^{63}-1$. Duplicate keys are ignored.

Examples

Input

5
1 2 3 4 5

Output

4

Explanation

The keys are inserted in increasing order, so every new node becomes a right descendant of the previous one. The resulting tree is a chain of $5$ nodes.

The path from root $1$ to leaf $5$ contains $4$ edges, so the tree height is $4$.