Chiều cao và BST suy biến (BST Height and Degeneration)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Dựng BST từ dãy $a_1,a_2,\ldots,a_n$ theo đúng thứ tự chèn; khóa trùng bị bỏ qua.

Độ sâu của gốc được quy ước bằng $0$. Độ sâu của một nút khác bằng số cạnh trên đường đi duy nhất từ gốc đến nút đó. Chiều cao của một cây không rỗng là độ sâu lớn nhất trong tất cả các nút của cây, hay tương đương là số cạnh trên đường dài nhất từ gốc đến một nút lá.

Theo quy ước của bài, cây rỗng có chiều cao $-1$.

Hãy tính chiều cao của BST sau khi chèn toàn bộ dãy.

Input

Dòng đầu chứa số nguyên $n$.

Nếu $n>0$, dòng tiếp theo chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$ theo thứ tự chèn. Nếu $n=0$, dòng này không xuất hiện.

Output

In một số nguyên duy nhất là chiều cao của cây.

Subtask

Subtask 1 (20 điểm): $0\le n\le 20$.

Subtask 2 (30 điểm): $0\le n\le 5000$.

Subtask 3 (50 điểm): $0\le n\le 200000$.

Trong tất cả các subtask, $-2^{63}\le a_i\le 2^{63}-1$. Khóa trùng bị bỏ qua khi dựng cây.

Ví dụ

Input

5
1 2 3 4 5

Output

4

Giải thích

Các khóa được chèn theo thứ tự tăng dần nên mỗi nút mới nằm ở phía phải của nút trước đó. Cây thu được là một đường gồm $5$ nút.

Đường từ gốc $1$ đến lá $5$ đi qua $4$ cạnh, vì vậy chiều cao của cây là $4$.