Sau khi được bạn giúp giải bài toán Dãy Con Tăng 1, Beo rất vui và kể lại với Cheow. Nhưng Cheow không dễ tính như vậy. Cậu ta đưa cho Beo một danh sách lớn hơn, gồm ~N~ số nguyên ~A_1, A_2,..., A_N~, và yêu cầu Beo giải nó, nhưng Beo vẫn không biết làm vì vậy Beo lại nhờ bạn.

Liệu bạn có thể tiếp tục giúp Beo vượt qua thử thách từ Cheow?

Input

• Dòng đầu tiên chứa một số nguyên dương ~N~ ~(1 ≤ N ≤ 10^5)~.
• 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

7
2 5 3 7 11 8 10

Output

5

💡 Explanation

Một dãy con tăng dần nghiêm ngặt có độ dài 5 là: 2 3 7 8 10. Có nhiều dãy đúng khác như 2 5 7 8 10 cũng có độ dài 5.