LIS - Dãy con tăng dài nhất (bản khó)

(Giống bài LIQ) Cho một dãy gồm N số nguyên (1 ≤ N ≤ 30000). Hãy tìm dãy con tăng dài nhất trong dãy đó và in ra số lượng phần tử của dãy con.

Các số trong phạm vi longint.

Input

• Dòng đầu tiên gồm số nguyên N.
• Dòng thứ hai gồm N số mô tả dãy.

Output

Gồm một số nguyên duy nhất là đáp số của bài toán (độ dài dãy con tăng dài nhất).

Example

Input

5
2 1 4 3 5

Output

3