Chia đội

Ở một vùng đất xa xôi, có một nhóm \(n\) nhà thám hiểm chuẩn bị cho một chuyến hành trình nguy hiểm. Mỗi nhà thám hiểm đứng thành một hàng thẳng và mặc một chiếc áo choàng ma thuật với một màu sắc đặc trưng. Màu sắc áo choàng của nhà thám hiểm thứ \(i\) được biểu diễn bởi \(a_i\).

Đội trưởng của nhóm, Sir Eldric, cần tổ chức các nhà thám hiểm thành các đội trước khi bắt đầu hành trình. Để đảm bảo sự hài hòa trong đội, Sir Eldric đưa ra các quy tắc sau:

• Mỗi đội phải bao gồm các nhà thám hiểm đứng liên tiếp trong hàng. Nghĩa là, nếu nhà thám hiểm \(i\) và \(j\) thuộc cùng một đội, thì tất cả các nhà thám hiểm \(k\) sao cho \((i \le k \le j)\) cũng phải thuộc đội đó.
• Mỗi đội không được có quá \(k\) màu áo choàng khác nhau, trong đó \(k\) là một tham số Sir Eldric đang cân nhắc.
• Mỗi đội cần một chỉ huy, và việc bổ nhiệm chỉ huy sẽ tốn kém. Vì vậy, Sir Eldric muốn tối thiểu hóa số lượng đội cần thành lập.

Trước khi đưa ra chiến lược cuối cùng, Sir Eldric muốn thử nghiệm với các giá trị khác nhau của \(k\). Với mỗi \(k\) từ \(1\) đến \(n\), hãy xác định số lượng đội tối thiểu cần thiết để thỏa mãn các điều kiện trên.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) \((1 \leq n \leq 10^5)\), số lượng nhà thám hiểm.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq n)\), biểu diễn màu áo choàng của các nhà thám hiểm.

Output

In ra \(n\) số nguyên. Số nguyên thứ \(i\) biểu diễn số lượng đội tối thiểu cần thiết khi \(k = i\).

Example

7
3 2 7 1 2 1 4

7 4 2 2 1 1 1 

Scoring

• Có \(20\%\) số điểm ứng với \(n \le 10^3\).
• \(80\%\) số điểm còn lại không có ràng buộc thêm.