Hệ thống chấm bài trực tuyến của Trường Công nghệ Thông tin và Truyền thông lưu lại kết quả ~n~ vòng luyện tập mà một sinh viên đã tham gia, theo đúng thứ tự thời gian: ở vòng thứ ~i~ sinh viên đạt ~a_i~ điểm.

Để làm hồ sơ xét khen thưởng, sinh viên muốn chọn ra một số vòng luyện tập tạo thành một chuỗi tiến bộ: các vòng được chọn giữ nguyên thứ tự thời gian (không nhất thiết phải liên tiếp nhau) và điểm của vòng được chọn sau phải cao hơn hẳn điểm của vòng được chọn ngay trước nó. Chuỗi chỉ gồm một vòng luôn được coi là chuỗi tiến bộ.

Yêu cầu

Hãy tìm số vòng nhiều nhất có thể có trong một chuỗi tiến bộ. Nói cách khác, tìm số ~k~ lớn nhất sao cho tồn tại các chỉ số ~1 \le i_1 < i_2 < \cdots < i_k \le n~ thoả mãn

$$a_{i_1} < a_{i_2} < \cdots < a_{i_k} .$$

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên dương ~n~;
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~, các số cách nhau bởi dấu cách.

Kết quả ra

Ghi ra một số nguyên duy nhất là số vòng nhiều nhất của một chuỗi tiến bộ.

Ràng buộc

~1 \le n \le 2 \cdot 10^5~; ~1 \le a_i \le 10^9~.

• Subtask 1 (20% số điểm – test 01–04): ~n \le 20~;
• Subtask 2 (30% số điểm – test 05–10): ~n \le 5000~;
• Subtask 3 (20% số điểm – test 11–14): ~a_i \le 100~;
• Subtask 4 (30% số điểm – test 15–20): không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào mẫu 1

8
3 1 4 4 5 2 6 6

Kết quả ra mẫu 1

4

Giải thích

Một chuỗi tiến bộ dài nhất gồm các vòng ~1, 3, 5, 7~ với số điểm ~3 < 4 < 5 < 6~. Không thể chọn cả hai vòng ~3~ và ~4~ vì chúng cùng ~4~ điểm (điểm phải cao hơn hẳn); tương tự với hai vòng ~7~ và ~8~. Không có chuỗi tiến bộ nào gồm ~5~ vòng.