문제
정수 0 이상인 숫자로 이루어진 배열 a가 주어집니다. 배열은 a₁, a₂, …, aₙ (1 ≤ N ≤ 2⋅10⁵, 0 ≤ aᵢ ≤ N)로 구성되어 있습니다. 한 번의 연산에서 배열의 임의의 원소를 임의의 0 이상의 정수로 바꿀 수 있습니다.
배열의 mex는 배열에 포함되지 않은 최소의 0 이상의 정수로 정의됩니다. 0부터 N까지의 각 정수 i에 대해, 배열 a의 mex를 i로 만들기 위해 필요한 최소 연산 횟수를 구하세요.
입력
첫 번째 줄에는 정수 N이 주어집니다.
다음 줄에는 공백으로 구분된 N개의 정수 a₁, a₂, …, aₙ이 주어집니다.
출력
0부터 N까지 (포함) 각 정수 i에 대해, 해당 mex를 만들기 위해 필요한 최소 연산 횟수를 한 줄에 하나씩 출력하세요. (어떤 i에 대해서도 mex를 만들 수 있음은 보장됩니다.)
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 50점 | |
| #2 | 50점 | 추가 제약 조건 없음 |
예제1
입력
4
2 2 2 0
출력
1
0
3
1
2
배열의 mex를 0으로 만들기 위해서는 예를 들어 a₄를 3(또는 임의의 양의 정수)로 바꾸면 됩니다. 변경된 배열 [2, 2, 2, 3]에서 0은 포함되지 않은 최소의 0 이상의 정수이므로 mex는 0이 됩니다.
mex를 1로 만들기 위해서는 변경할 필요가 없습니다. 배열 [2, 2, 2, 0]에는 1이 이미 포함되어 있지 않기 때문에 mex가 1입니다.
mex를 2로 만들기 위해서는 배열의 처음 세 원소를 변경해야 합니다. 예를 들어, 배열 a를 [3, 1, 1, 0]으로 바꾸면 mex는 2가 됩니다.
출처
USACO 2025 February Bronze