Cho một dãy số nguyên gồm N phần tử A[1], A[2],.. A[N]. Biết rằng dãy con tăng đơn điệu là một dãy A[i1],.. A[ik] thỏa mãn i1< i2< … <ik và A[i1] < A[i2] < … <A[ik]. Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy là bao nhiêu phần tử ?

Ví dụ: 

Cho dãy số sau: 1 9 2 5 4 2 6 3. Dãy con dài nhất thỏa mãn điều kiện là: 1 2 5 6 và 1 2 4 6, hai dãy con này đều có độ dài là 4.

Input: 

       Dòng 1: số nguyên N

       Dòng 2: N số nguyên A[1], A[2],..., A[N]

Output:

       Độ dài dãy con đơn điệu dài nhất.