Dãy con của một dãy là dãy có thể đạt được bằng cách xoá đi một số phần tử trong dãy ban đầu. Dãy rỗng và dãy ban đầu cũng là dãy con của dãy ban đầu. Bài toán tìm một dãy con tăng dài nhất trong một tập các phần tử là tìm một dãy con của dãy ban đầu sao cho trong dãy con này phần tử đứng sau lớn hơn hẵn phần tử đứng trước. Dãy con này không cần thiết phải liền kề, hoặc là duy nhất.

Bài toán dãy con tăng dài nhất được áp dụng rộng rãi ở nhiều lĩnh vực: Toán học (thuật toán, lý thuyết ma trận, lý thuyết đại diện) hay Vật Lý. Trong bài tập này nhiệm vụ của bạn cần thực hiện là viết chương trình nhận đầu vào là một dãy số nguyên có \(N\) phần tử \(A_1,A_2,..A_N\), tìm dãy con tăng dài nhất của dãy đã cho.

Dữ liệu vào

• Dòng đầu tiên là số nguyên dương \(N\) \((1 \le N \le 5000)\)
• Dòng thứ hai chứa \(N\) số nguyên thuộc dãy \(A\) \((|A_i| \le 10^9)\)

Dữ liệu ra

• Ghi ra một số nguyên là độ dài dãy con tăng dài nhất tìm được.

Input 1

5
1 1 3 4 1

Output 1

3