Beo tìm thấy một danh sách gồm ~N~ con số mà Talulu để quên trong sổ tay. Danh sách gồm các số nguyên ~A_1, A_2,..., A_N~. Beo muốn chọn ra một số con số trong đó (không cần liên tiếp) sao cho các số được chọn tăng dần một cách nghiêm ngặt (tức là mỗi số phía sau phải lớn hơn số phía trước), và Beo muốn dãy số được chọn dài nhất có thể.

Bạn hãy giúp Beo tìm độ dài lớn nhất của một dãy con tăng dần nghiêm ngặt có thể chọn ra từ danh sách của Talulu.

Input

• Dòng đầu tiên chứa một số nguyên dương ~N~ ~(1 ≤ N ≤ 5000)~.
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2,..., A_N~ ~(1 ≤ A_i ≤ 10^{6})~.

Output

• In ra một số nguyên duy nhất là độ dài lớn nhất của dãy con tăng dần nghiêm ngặt có thể chọn.

📌 Example

Input

6
3 1 4 2 5 6

Output

4

💡 Explanation

Một trong các dãy con tăng dần dài nhất là: 1 2 5 6, độ dài là 4. Dãy 3 4 5 6 cũng đúng nhưng không dài hơn.