Xếp Tháp Đĩa Nhựa

General
Points
30
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
array1d
Submissions
Đề bài

Bạn nhận được $N$ chiếc đĩa nhựa theo thứ tự, chiếc đĩa thứ $i$ có bán kính $R_i$. Bạn phải xếp lần lượt từng chiếc đĩa vào các chồng đĩa. Một chiếc đĩa chỉ có thể đặt lên trên một chồng nếu bán kính của nó nhỏ hơn hẳn bán kính của chiếc đĩa đang nằm trên đỉnh chồng đó; nếu không, bạn có thể tạo một chồng mới. Hãy tìm số lượng chồng đĩa ít nhất có thể.

Dữ liệu vào
  • Dòng đầu chứa số nguyên $N$.
  • Dòng thứ hai chứa $N$ số nguyên $R_1, R_2, \dots, R_N$.
Dữ liệu ra

Một số nguyên duy nhất là số chồng đĩa ít nhất.

Ví dụ
Input Output
5
3 8 2 1 5
2
Giới hạn
  • $1 \le N \le 2 \cdot 10^5$.
  • $1 \le R_i \le 10^9$.
Draft saved