309066: CF1619E. MEX and Increments
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
MEX and Increments
题意翻译
给你一个数列,每次可以花费 $1$ 代价将其中一个数加一。从 $0$ 到 $n$ 分别输出至少要花费多少才能使这个数是数列中没有出现的最小的非负整数。题目描述
Dmitry has an array of $ n $ non-negative integers $ a_1, a_2, \dots, a_n $ . In one operation, Dmitry can choose any index $ j $ ( $ 1 \le j \le n $ ) and increase the value of the element $ a_j $ by $ 1 $ . He can choose the same index $ j $ multiple times. For each $ i $ from $ 0 $ to $ n $ , determine whether Dmitry can make the $ \mathrm{MEX} $ of the array equal to exactly $ i $ . If it is possible, then determine the minimum number of operations to do it. The $ \mathrm{MEX} $ of the array is equal to the minimum non-negative integer that is not in the array. For example, the $ \mathrm{MEX} $ of the array $ [3, 1, 0] $ is equal to $ 2 $ , and the array $ [3, 3, 1, 4] $ is equal to $ 0 $ .输入输出格式
输入格式
The first line of input data contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases in the input. The descriptions of the test cases follow. The first line of the description of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the length of the array $ a $ . The second line of the description of each test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i \le n $ ) — elements of the array $ a $ . It is guaranteed that the sum of the values $ n $ over all test cases in the test does not exceed $ 2\cdot10^5 $ .
输出格式
For each test case, output $ n + 1 $ integer — $ i $ -th number is equal to the minimum number of operations for which you can make the array $ \mathrm{MEX} $ equal to $ i $ ( $ 0 \le i \le n $ ), or -1 if this cannot be done.
输入输出样例
输入样例 #1
5
3
0 1 3
7
0 1 2 3 4 3 2
4
3 0 0 0
7
4 6 2 3 5 0 5
5
4 0 1 0 4
输出样例 #1
1 1 0 -1
1 1 2 2 1 0 2 6
3 0 1 4 3
1 0 -1 -1 -1 -1 -1 -1
2 1 0 2 -1 -1