Cho một dãy số nguyên ~A~ gồm ~n~ phần tử ~(1 ≤ n ≤ 10^5)~ được đánh số từ ~1~ đến ~n~. Hãy tìm một dãy con có nhiều phần tử nhất của ~A~ sao cho dãy con đó là một dãy số tăng dần.

Yêu cầu:

Tìm độ dài lớn nhất của dãy con tăng dần (LIS).

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên ~n~ - số phần tử của dãy.
• Dòng thứ hai chứa ~n~ số nguyên ~A_1, A_2, ..., A_n~ ~(-10^9 ≤ A_i ≤ 10^9)~.

Dữ liệu ra:

• Dòng đầu tiên in ra độ dài của dãy con tăng dài nhất.

Ví dụ 1

Input:

7
5 9 6 7 2 1 8

Output:

4