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에 대해 양 끝값을 포함하여 필요한 요새의 최소 개수를 알아야 한다.

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

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

입력의 첫 번째이자 유일한 줄에 공백으로 구분된 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]$