Cho một dãy số nguyên gồm N phần tử a1,a2,…,a_N. Yêu cầu: Tìm số nguyên dương K lớn nhất thỏa mãn tồn tại ~(i_1,i_2,…,i_K ) mà 1≤i_1<i_2<⋯<i_K≤N và a_(i_1 )<a_(i_2 )<⋯<a_(i_k ).~</p>

Input:

Dòng đầu tiên gồm một số nguyên dương N (N≤5000);

Dòng tiếp theo gồm N số nguyên a_1,a_2,…,a_N  (|a_i |≤〖10〗^9 ).

Output: In ra giá trị K lớn nhất.

Ví dụ:
DP_B1.INP       DP_B1.OUT
5
1 4 3 2 5           3