Cho một dãy số nguyên gồm ~N~ phần tử ~A1, A2, . . . , AN~ . Biết rằng dãy con tăng đơn điệu là một dãy ~A{i1}, A{i2}, ..., A{ik}~ thỏa mãn ~i1 < i2 <...< ik~ và ~A_{i1} < A{i2} < ...< 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 ~A1, A2, . . . , AN~ ~(1 ≤ Ai ≤ 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 ~A1 = 1 < A2 = 2 < A4 = 4 < A5 = 6~, độ dài dãy này là ~4~.