Các tháp khối (Towers)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ khối lập phương được đưa đến theo một thứ tự cố định. Khi đặt một khối lên trên một tháp, kích thước của khối mới phải nhỏ hơn khối đang ở đỉnh tháp.

Mỗi khối khi đến phải được xử lý ngay: hoặc đặt lên một tháp hiện có, hoặc bắt đầu một tháp mới.

Hãy tìm số tháp nhỏ nhất có thể tạo sau khi xử lý toàn bộ các khối.

Input

Dòng đầu chứa $n$.

Dòng thứ hai chứa $n$ số $k_1,\ldots,k_n$, kích thước các khối theo thứ tự xuất hiện.

Output

In số tháp nhỏ nhất.

Subtask

• Subtask 1 — 20%: $n\le1000$.
• Subtask 2 — 30%: $n\le50000$.
• Subtask 3 — 50%: $1\le n\le2\cdot10^5$, $1\le k_i\le10^9$.

Ví dụ

Input

5
3 8 2 1 5

Output

2

Giải thích

Xử lý theo thứ tự $3,8,2,1,5$:

• đặt $3$ vào tháp thứ nhất;
• khối $8$ không thể đặt lên $3$ vì $8>3$, nên mở tháp thứ hai;
• đặt $2$ lên trên $3$, rồi đặt $1$ lên trên $2$;
• đặt $5$ lên trên $8$.

Ta dùng được $2$ tháp. Một tháp là không thể vì sau khi khối $3$ xuất hiện, khối $8$ lớn hơn không thể đặt lên trên nó.