페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8185
서브태스크
다국어

독사 연합 2초 1024MB

문제

뱀 N마리는 일렬로 배치되어 있으며, i번째 뱀은 a_i​라는 독의 종류를 갖는다.
뱀들은 다음 조건을 만족할 때 독사 연합(poison snake alliance)을 형성할 수 있다:

  • 같은 독의 종류를 가진 뱀들로만 구성된다.

  • 연합 내의 모든 뱀들은 서로 x마리 이하의 거리로 떨어져 있어야 한다. 여기서 x는 [1, N] 범위 내의 정수다.

  • 모든 뱀은 정확히 하나의 독사 연합에 속해야 한다.

각 x에 대해, 형성될 수 있는 최소 독사 연합의 수를 계산하시오.


입력

첫 줄에 정수 N이 주어진다. (1≤N≤10^5)

다음 줄에 N개의 정수 a_1, \cdots, a_N이 주어진다. (1≤a_i≤N)


출력

1부터 N까지의 각각의 x에 대하여 형성될 수 있는 최소 독사 연합의 수를 각 줄에 순서대로 출력한다.


부분문제

번호 점수 조건
#110점

N \le 5000

#220점

a_i \le 10

#330점

독의 종류가 최대 10번까지만 중복된다.

#440점

추가 제약 조건 없음


예제1

입력
9
111921211
출력
7
5
4
4
4
4
4
3
3

x=1인 경우와 x=2 인 경우를 보면 아래와 같이 여러 구성으로 그룹이 형성될 수 있다. (각 알파벳은 서로 다른 독사 연합을 의미한다)

Example:

       1 1 1 9 2 1 2 1 1
x = 1: A B B C D E F G G (7 개의 독사 연합)
x = 1: A A B C D E F G G (7 개의 독사 연합)
x = 2: A A A B C D C E E (5 개의 독사 연합)
x = 2: A A A B C D C D E (5 개의 독사 연합)

출처

USACO 2024 December Gold

역링크