\(N\) (\(1\leq N\leq 10^5\)) cô bò của Farmer John được xếp thành một hàng. Cô bò thứ \(i\) có nhãn \(a_i\) (\(1\leq a_i\leq N\)). Một nhóm bò có thể tạo thành một nhóm bạn nếu tất cả có cùng nhãn và mỗi cô bò cách mọi cô bò khác trong nhóm không quá \(x\) cô bò, trong đó \(x\) là một số nguyên thuộc \([1,N]\). Mỗi cô bò phải thuộc đúng một nhóm bạn.

Với mỗi \(x\) từ \(1\) đến \(N\), hãy tính số nhóm bạn nhỏ nhất có thể được tạo thành.

Dữ liệu vào

Dòng đầu chứa một số nguyên \(N\).

Dòng tiếp theo chứa \(a_1\dots a_N\), là nhãn của từng cô bò.

Dữ liệu ra

Với mỗi \(x\) từ \(1\) đến \(N\), in trên một dòng mới số nhóm bạn nhỏ nhất ứng với \(x\) đó.

Phân nhóm

• Các test 2–3: \(N\leq 5000\).
• Các test 4–7: \(a_i\leq 10\) với mọi \(i\).
• Các test 8–11: Không nhãn nào xuất hiện quá \(10\) lần.
• Các test 12–20: Không có ràng buộc bổ sung.

Ví dụ

9
1 1 1 9 2 1 2 1 1

7
5
4
4
4
4
4
3
3

       1 1 1 9 2 1 2 1 1
x = 1: A B B C D E F G G (7 nhóm)
x = 1: A A B C D E F G G (7 nhóm, một cách chia khác)
x = 2: A A A B C D C E E (5 nhóm)
x = 2: A A A B C D C D E (5 nhóm, một cách chia khác)

Nguồn

Đề bài gốc: USACO 2024 December Contest, Gold — Cowdependence

Tác giả: Chongtian Ma.