Codeforces Round 762 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

data structures

dp

greedy

implementation

math

sortings

*1700

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. MEX and Increments

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputDmitry 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$$$.

Input

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$$$.

Output

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.

Example

Input

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

Output

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

Note

In the first set of example inputs, $$$n=3$$$:

- to get $$$\mathrm{MEX}=0$$$, it is enough to perform one increment: $$$a_1$$$++;
- to get $$$\mathrm{MEX}=1$$$, it is enough to perform one increment: $$$a_2$$$++;
- $$$\mathrm{MEX}=2$$$ for a given array, so there is no need to perform increments;
- it is impossible to get $$$\mathrm{MEX}=3$$$ by performing increments.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/18/2024 11:39:33 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|