Cồn Nổi là một đảo thuộc vùng biển huyện Kim Sơn, tỉnh Ninh Bình. Nơi đây đang được đầu tư xây dựng và hứa hẹn trở thành một điểm du lịch, nghỉ dưỡng hấp dẫn. Trong một lần đến thăm Cồn Nổi, Minh Dương đi dạo dọc bờ biển và nhặt được những vỏ ốc có kích thước tương ứng là các số ~a_1,a_2,…,a_n~. Minh Dương muốn lựa chọn một số vỏ ốc để xâu lại thành một chuỗi, sao cho khi tính từ đầu chuỗi đến cuối chuỗi các vỏ ốc phía sau có kích thước lớn hơn vỏ ốc phía trước.

Yêu cầu: Hãy tìm số vỏ ốc nhiều nhất mà Minh Dương có thể chọn được.

Dữ liệu vào:

• Dòng đầu là số nguyên dương ~n~ (~n ≤ 10^6~).
• Dòng thứ hai ghi dãy các số nguyên dương ~a_1,a_2,…,a_n~ (~a_i \le 10^9, 1 \le i \le n~).

Dữ liệu ra:

• Ghi số vỏ ốc nhiều nhất mà Minh Dương có thể xâu được thành chuỗi.

Ví dụ:

Input1

6
6 5 8 8 3 6

Output1

4

Input2

8
6 1 2 2 7 6 2 5

Output2

5

Ràng buộc:

• 60% test với ~0 \le n,a_i \le 10^3~;
• 20% test với ~10^3 < n,a_i \le 10^5~;