Chu có một mảng chứa ~n~ số nguyên. Cậu ấy sẽ tạo ra mảng ~A~ bằng cách xét các số trên mảng ban đầu từ trái sang phải, sau đó thêm số đó vào đầu hoặc cuối mảng ~A~. Nhiệm vụ của Chu là tạo ra một mảng ~A~ sao cho ~LIS(A)~ là lớn nhất. Với ~LIS(A)~ là hàm đưa ra độ dài của dãy con tăng dài nhất trong mảng ~A~.

Input

• Dòng đầu tiên gồm số ~n~.
• Dòng tiếp theo chứa ~n~ số nguyên dương không quá ~10^9~ là các số trên bảng.

Output

• In ra ~LIS(A)~ lớn nhất.

Sample Input 1

4
2 1 3 4

Sample Output 1

4