Per được cho một mảng gồm ~n~ số nguyên.

Nhiệm vụ của Per là tìm dãy con tăng ngặt dài nhất của mảng, tức là dãy con dài nhất mà mỗi phần tử đều lớn hơn phần tử đứng ngay trước nó.

Một dãy con là dãy thu được từ mảng ban đầu bằng cách xóa đi một số phần tử (có thể không xóa phần tử nào) mà không làm thay đổi thứ tự của các phần tử còn lại.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~n~ — số phần tử của mảng.
• Dòng thứ hai chứa ~n~ số nguyên ~x_1, x_2, \ldots, x_n~ — các phần tử của mảng.

Kết quả

In ra độ dài của dãy con tăng ngặt dài nhất.

Ví dụ

Đầu vào:

8
7 3 5 3 6 2 9 8

Đầu ra:

4

Giải thích: Một dãy con tăng dài nhất là ~3, 5, 6, 9~.

Giới hạn

• ~1 \le n \le 2 \cdot 10^5~
• ~1 \le x_i \le 10^9~

Gọi ~f_i~ là độ dài dãy con tăng dài nhất kết thúc tại vị trí ~i~. Khi đó ~f_i = 1 + \max f_j~ với ~j < i~ và ~x_j < x_i~. Hãy nén giá trị rồi dùng một cấu trúc dữ liệu lấy ~\max~ trên tiền tố để tính ~f_i~ trong ~O(\log n)~.