Mô tả và yêu cầu

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 ai1, ai2, ..., aik thỏa mãn i1 < i2 < ... < ik và ai1 < ai2 < ... < aik.

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ữ liệu vào: SEQ7.inp

Dòng 1 gồm 1 số nguyên là số N.

Dòng thứ 2 ghi N số nguyên a1, a2, ..., an.

Dữ liệu ra

Kết quả: SEQ7.out

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

Giới hạn và chấm điểm

1 ≤ ai ≤ 10^9.

Sub1: n < 5000.

Sub2: n <= 500000.

Ví dụ

7
8 -10 6 -5 9 1 12

4

Dãy con đơn điệu độ dài 4 ví dụ là dãy (-10, -5, 1, 12).