Cho dãy số nguyên ~A = {a_1, a_2, ..., a_n}~. Một dãy con của dãy A là một cách chọn ra trong A một số phần tử giữ nguyên thứ tự. Như vậy A có ~2^n~ dãy con.

Yêu cầu:

Tìm dãy con đơn điệu tăng của A có độ dài lớn nhất. Tức là tìm một số K lớn nhất sao cho tồn tại một dãy chỉ số ~i_1 < i_2 < ... < i_k ~ sao cho ~a_{i_1} < a_{i_2} < ... < a_{i_k}~

Dữ liệu:

Dòng đầu chứa số nguyên dương n ~(n \le 10^5)~
Dòng tiếp theo chứa n số nguyên ~a_i~ ~(\forall i, |a_i| \le 10^9)~

Kết quả:

Một dòng duy nhất ghi giá trị của K.

Input:

12
1 2 3 8 9 4 5 6 2 3 9 10

Output:

8

Tham khảo:

Các phương pháp tiếp cận bài LIS || link 2