Dãy con tăng dài nhất

Cho một dãy số nguyên gồm \(N\) phần tử \(A[1], A[2], \ldots, A[N]\).

Một dãy con tăng đơn điệu là một dãy \(A[i_1], A[i_2], \ldots, A[i_k]\) thoả mãn \(i_1 < i_2 < \ldots < i_k\) và \(A[i_1] < A[i_2] < \ldots < A[i_k]\).

Yêu cầu: Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy đã cho có bao nhiêu phần tử.

Input

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 10^5\)).

• Dòng thứ hai chứa \(N\) số nguyên \(A[1], A[2], \ldots, A[N]\) (\(0 \le A[i] \le 10^6\)).

Output

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

Scoring

• Có \(30\%\) số điểm ứng với \(N \le 10^3\).

• \(70\%\) số điểm còn lại ứng với \(N \le 10^5\).