(Giống bài LIQ - Longest Increasing Subsequence (Ezz), nhưng khó hơn)

Cho một dãy số nguyên gồm ~n~ phần tử ~a_1, a_2, \dots, a_n~.

Biết rằng dãy con tăng đơn điệu là ~1~ dãy ~a_{i_{1}}, \dots, a_{i_{k}}~ thỏa mãn ~i_{1} < i_{2} < \dots < i_{k}~ và ~a_{i_{1}} < a_{i_{2}} < \dots < a_{i_{k}}~. 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 Specification

• Dòng thứ nhất gồm ~1~ số nguyên là số ~n~ ~(1 \le n \le 30000)~.
• Dòng thứ hai ghi ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le \max{ \{ \text{long int}, \text{long long} \} })~.

Output Specification

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

Sample Cases

Input #1:

5
2 1 4 3 5

Output #1:

3