Making Mexes

시간 제한2초메모리 제한2048 MB

요약

각 i=0부터 N까지, 배열이 0부터 i-1을 모두 포함하고 i를 포함하지 않도록 바꿔야 하는 원소 개수의 최솟값을 구한다.

난이도: 보통10점 중 6점
유형: 그리디, 누적 합, 정렬
정답자: 아직 제출이 없습니다

문제

You are given an array $a$ of $N$ non-negative integers $a\_1, a\_2, \dots, a\_N$ ( $1\le N\le 2\cdot 10^5, 0\le a\_i\le N$ ). In one operation, you can change any element of $a$ to any non-negative integer.

The mex of an array is the minimum non-negative integer that it does not contain. For each $i$ in the range $0$ to $N$ inclusive, compute the minimum number of operations you need in order to make the mex of $a$ equal $i$ .

입력

The first line contains $N$ .

The next line contains $a\_1,a\_2,\dots, a\_N$ .

출력

For each $i$ in the range $0$ to $N$ , output the minimum number of operations for $i$ on a new line. Note that it is always possible to make the mex of $a$ equal to any $i$ in the range $0$ to $N$ .

예제1

예제 1
입력
```
4
2 2 2 0
```
예상 출력
```
1
0
3
1
2
```