У Дмитрия есть массив из \(n\) неотрицательных целых чисел \(a_1, a_2, \dots, a_n\).
За одну операцию он может выбрать произвольный индекс \(j\) (\(1 \le j \le n\)) и увеличить значение элемента \(a_j\) на \(1\). Он может выбирать один и тот же индекс \(j\) многократно.
Для каждого \(i\) от \(0\) до \(n\) определите, сможет ли Дмитрий сделать \(\mathrm{MEX}\) массива равным ровно \(i\). Если сможет, то определите, за какое минимальное количество операций.
\(\mathrm{MEX}\) массива равен минимальному целому неотрицательному числу, которого нет в массиве. Например, \(\mathrm{MEX}\) массива \([3, 1, 0]\) равен \(2\), а массива \([3, 3, 1, 4]\) — \(0\).
Выходные данные
Для каждого набора входных данных выведите \(n + 1\) целое число — \(i\)-е число равно минимальному числу операций, за которое можно сделать \(\mathrm{MEX}\) массива равным \(i\) (\(0 \le i \le n\)), или -1, если этого сделать нельзя.
Примечание
В первом наборе входных данных примера \(n=3\):
- чтобы получить \(\mathrm{MEX}=0\), достаточно выполнить один инкремент: \(a_1\)++;
- чтобы получить \(\mathrm{MEX}=1\), достаточно выполнить один инкремент: \(a_2\)++;
- \(\mathrm{MEX}=2\) для заданного массива, поэтому выполнять инкременты не надо;
- получить \(\mathrm{MEX}=3\), выполняя инкременты, невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
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 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
|