Cho dãy ~a_1, a_2, \dots, a_n~. Hãy tìm độ dài của dãy con tăng nghiêm ngặt dài nhất (LIS).

Input

• Dòng 1: ~n~ trong đó ~1 \le n \le 5000~
• Dòng 2: ~n~ số nguyên ~a_i~ trong đó ~|a_i| \le 10^9~

Output

• Một số nguyên: độ dài LIS.

Ví dụ

Input

8
3 1 2 1 8 5 6 2

Output

4