Till I Collapse

Rick and Morty은 MR을 찾고 싶어 한다. PBH 그리고 그들만으로는 할 수 없다. 따라서 그들에게는 Mr. Meeseeks가 필요하다. They Have은 1부터 n까지 번호가 매겨진 줄에 서 있는 n명의 Mr. Meeseeks를 생성했다. 이들은 각자 자신의 색을 가지고 있다. i-th번째 Mr. Meeseeks의 색은 ai이다.

Rick and Morty은 군대를 모으고 있으며 Mr. Meeseeks를 몇 개의 분대로 나누고 싶어 한다. 분대가 지나치게 다채로운 것은 원하지 않으므로, 각 분대에는 최대 k가지 서로 다른 색의 Mr. Meeseeks가 있어야 한다. 또한 각 분대는 줄에 선 Mr. Meeseeks의 연속 부분 배열이어야 한다. 즉, 모든 1 ≤ i ≤ e ≤ j ≤ n에 대해, i번 Mr. Meeseeks와 j번 Mr. Meeseeks가 같은 분대에 속한다면 e번 Mr. Meeseeks도 그 분대에 속해야 한다.

또한 각 분대에는 자체 주둔지가 필요하고, 주둔지를 건설하려면 돈이 필요하므로, 이들은 분대의 총개수를 최소화하고 싶어 한다.

Rick and Morty은 아직 k의 정확한 값을 확정하지 않았으므로, 이를 선택하기 위해 1부터 n까지의 각 k에 대해 필요한 주둔지의 최소 개수를 알아야 한다(양 끝 포함).

입력의 첫 번째 줄에는 하나의 정수 n (1 ≤ n ≤ 105)가 주어진다. Mr. Meeseeks의 수이다.

두 번째 줄에는 공백으로 구분된 n개의 정수 a1, a2, ..., an (1 ≤ ai ≤ n)가 주어진다. Mr. Meeseeks가 줄에 서 있는 순서대로의 색이다.

입력의 첫 번째이자 유일한 줄에 공백으로 구분된 n개의 정수를 출력한다. i-th번째 정수는 k의 값이 i일 때 필요한 주둔지의 최소 개수여야 한다.

첫 번째 예제 테스트 케이스에서, 각 k에 대해 군대를 분대로 나누는 몇 가지 최적의 방법은 다음과 같다.

1. $[1]$, $[3]$, $[4]$, $[3, 3]$
2. $[1]$, $[3, 4, 3, 3]$
3. $[1, 3, 4, 3, 3]$
4. $[1, 3, 4, 3, 3]$
5. $[1, 3, 4, 3, 3]$

두 번째 테스트 케이스에서, 각 k에 대해 군대를 분대로 나누는 몇 가지 최적의 방법은 다음과 같다.

1. $[1]$, $[5]$, $[7]$, $[8]$, $[1]$, $[7]$, $[6]$, $[1]$
2. $[1, 5]$, $[7, 8]$, $[1, 7]$, $[6, 1]$
3. $[1, 5, 7]$, $[8]$, $[1, 7, 6, 1]$
4. $[1, 5, 7, 8]$, $[1, 7, 6, 1]$
5. $[1, 5, 7, 8, 1, 7, 6, 1]$
6. $[1, 5, 7, 8, 1, 7, 6, 1]$
7. $[1, 5, 7, 8, 1, 7, 6, 1]$
8. $[1, 5, 7, 8, 1, 7, 6, 1]$