Cho một dãy số nguyên gồm ~N~ phần tử ~A_1, A_2, . . . , A_N~ . Biết rằng dãy con tăng đơn điệu là một dãy ~A_{i_1}, A_{i_2}, ..., A_{i_k}~ thỏa mãn ~i_1 < i_2 <...< i_k~ và ~A_{i_1} < A_{i_2} < ...< A_{i_k}~ . Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử?

Dữ liệu vào

• Dòng đầu gồm ~1~ số nguyên là số ~N~ ~(1 ≤ N ≤ 1000)~.
• Dòng tiếp theo ghi ~N~ số nguyên ~A_1, A_2, . . . , A_N~ ~(1 ≤ A_i ≤ 10000)~.

Dữ liệu ra

Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.

Sample Input

6
1 2 5 4 6 2

Sample Output

4

Giải thích

Dãy con dài nhất là dãy ~A_1 = 1 < A_2 = 2 < A_4 = 4 < A_5 = 6~, độ dài dãy này là ~4~.