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à 1 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 này có bao nhiêu phần tử?

Input

• Dòng 1 gồm 1 số nguyên là số N (1 ≤ N ≤ 23000).

• Dòng thứ 2 ghi N số nguyên A[1], A[2], .. A[N] (1 ≤ A[i] ≤ 10000000).

Output

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

Ví dụ

Input

10
5 2 3 4 9 10 5 6 7 3

Output

6