Chia đoạn theo số màu

Cho một dãy gồm $n$ số nguyên dương $a_1,a_2,\dots ,a_n$, mỗi số là một "màu" trong khoảng $1\le a_i\le n$.

Với một số nguyên dương $k$, ta cần chia dãy thành ít nhất các đoạn con liên tiếp sao cho mỗi đoạn chứa không quá $k$ giá trị phân biệt. Gọi $f(k)$ là số đoạn tối thiểu cần thiết.

Yêu cầu: với mọi $k=1,2,\dots ,n$, hãy tính giá trị $f(k)$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số phần tử của dãy.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ cách nhau bởi dấu cách.

Dữ liệu ra

In ra một dòng gồm $n$ số nguyên $f(1),f(2),\dots ,f(n)$ cách nhau bởi dấu cách.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le a_i\le n$
• Thời gian: $2$ giây. Bộ nhớ: $256$ MB.
• Bài này chỉ chấp nhận lời giải C++.

Ví dụ