G. Максимизируйте сумму
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Эта задача отличается от задачи B. В этой задаче вы должны вывести максимальную сумму минимумов префиксов для всех операций, которые стоят как минимум $$$x$$$, для каждого целого числа $$$x$$$ от $$$0$$$ до $$$n-1$$$.

Вам дан массив $$$a$$$ длиной $$$n$$$, элементы которого удовлетворяют условию $$$\boldsymbol{0 \le a_i \le n}$$$. Вы можете выполнить следующую операцию не более одного раза:

  • Выберите два индекса $$$i$$$ и $$$j$$$, такие что $$$i \lt j$$$. Присвойте $$$a_i := a_i + a_j$$$. Затем присвойте $$$a_j = 0$$$.

Стоимость выполнения операции равна $$$j-i$$$. Стоимость невыполнения операции равна $$$0$$$.

Для каждого целого числа $$$x$$$ от $$$0$$$ до $$$n-1$$$ включительно выведите максимально возможное значение $$$\min(a_1) + \min(a_1,a_2) + \ldots + \min(a_1, a_2, \ldots, a_n)$$$ среди всех возможных операций, которые имеют стоимость как минимум $$$x$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \leq n \leq 10^6$$$) — длина массива $$$a$$$.

Следующая строка содержит $$$n$$$ целых чисел, разделенных пробелами $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$) — массив $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Выходные данные

Для каждого набора входных данных на отдельной строке выведите $$$n$$$ целых чисел: $$$i$$$-е число обозначает максимальный ответ среди всех операций, которые имеют стоимость как минимум $$$i-1$$$.

Пример
Входные данные
6
2
1 2
4
2 3 1 4
2
1 0
5
5 5 0 5 5
5
4 1 3 3 1
10
7 4 7 0 8 7 5 0 2 1
Выходные данные
3 3 
10 10 10 10 
1 1 
20 20 20 15 15 
11 11 11 10 8 
27 27 27 27 23 23 20 19 17 16
Примечание

Давайте проанализируем пятый набор входных данных:

  • $$$x=0,1,2$$$: оптимальная операция это $$$i=2$$$ и $$$j=4$$$, она имеет стоимость $$$2$$$. Массив $$$a$$$ становится $$$[4,4,3,0,1]$$$, что дает результат $$$11$$$.
  • $$$x=3$$$: оптимальная операция это $$$i=2$$$ и $$$j=5$$$, она имеет стоимость $$$3$$$. Массив $$$a$$$ становится $$$[4,2,3,3,0]$$$, что дает результат $$$10$$$.
  • $$$x=4$$$: оптимальная (и единственная) операция это $$$i=1$$$ и $$$j=5$$$, она имеет стоимость $$$4$$$. Массив $$$a$$$ становится $$$[5,1,3,3,0]$$$, что дает результат $$$8$$$.