Cho một dãy số gồm ~n~ phần tử. Tìm độ dài của dãy con tăng dài nhất. Một dãy con được tạo bằng cách xóa đi một vài phần tử (hoặc không xóa) khỏi dãy ban đầu.

Yêu cầu: Tìm độ dài của dãy con tăng dài nhất.

Input

• Dòng thứ nhất chứa một số nguyên dương ~n~ (~n \leq 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1,a_2,...,a_n~ (~|a_i| \leq 10^9~).

Output

Kết quả cần tìm - độ dài của dãy con tăng dài nhất của dãy ~a~.

Scoring

• Subtask ~1~ ~(20\%)~: ~n \leq 20~;
• Subtask ~2~ ~(30\%)~: ~n \leq 2000~;
• Subtask ~3~ ~(50\%)~: ~n \leq 10^5~.

Example input 1

5
2 1 4 3 5

Example output 1

3