F2. Велосипедный спорт (сложная версия)
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Разница между версиями заключается в том, что в этой версии $$$1\le n\le 10^6$$$, и вам нужно вывести ответ для каждого префикса. Вы можете совершать взломы только в том случае, если решены все версии этой задачи.

Лео работает программистом в центре города, а его возлюбленная преподает в средней школе на окраине. Каждые выходные Лео ездит на своем велосипеде в пригород, чтобы провести приятные выходные с любимой.

Сейчас на этой дороге перед Лео едет $$$n$$$ велосипедистов. Они пронумерованы $$$1$$$, $$$2$$$, $$$\ldots$$$, $$$n$$$ от передней части к задней. Изначально Лео находится позади $$$n$$$-го велосипедиста. У $$$i$$$-го велосипедиста есть значение ловкости $$$a_i$$$.

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

  • Предположим, что первым перед Лео находится велосипедист $$$i$$$, тогда он может обогнать велосипедиста $$$i$$$ за стоимость $$$a_i$$$. Это ставит его позади велосипедиста $$$i - 1$$$.
  • Используя свои суперспособности, обменять $$$a_i$$$ и $$$a_j$$$ ($$$1\le i \lt j\le n$$$) за стоимость $$$(j - i)$$$.

Лео хочет узнать минимальную стоимость, чтобы оказаться перед $$$1$$$-м велосипедистом.

Кроме того, он хочет знать ответ для каждого $$$1\le i \le n$$$, $$$[a_1, a_2, \ldots, a_i]$$$ как исходный массив. Задачи для разных $$$i$$$ независимы. Более конкретно, в $$$i$$$-й задаче Лео начинает позади $$$i$$$-го велосипедиста вместо $$$n$$$-го, и велосипедисты с номерами $$$i + 1, i + 2, \ldots, n$$$ отсутствуют.

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

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

Первая строка каждого набора входных данных содержит целое положительное число $$$n$$$ ($$$1 \leq n \leq 10^6$$$), представляющее количество велосипедистов.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

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

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел, ответы для массива $$$[a_1, a_2, \ldots, a_i]$$$ для каждого $$$i = 1, 2, \ldots n$$$ в этом порядке.

Пример
Входные данные
4
3
1 2 4
4
1 1 1 1
2
1 2
4
4 1 3 2
Выходные данные
1 3 7
1 2 3 4
1 3
4 3 6 8
Примечание

В первом наборе входных данных одним из возможных способов из позиции позади $$$n$$$-го велосипедиста попасть на позицию перед $$$1$$$-м велосипедистом может быть:

  • Лео меняет местами $$$a_2$$$ $$$(i=2)$$$ и $$$a_3$$$ $$$(j=3)$$$, тогда массив становится $$$[1,4,2]$$$, это стоит $$$j-i=3-2=1$$$.
  • Лео переходит на позицию позади $$$2$$$-го велосипедиста с позиции позади $$$3$$$-го велосипедиста; это стоит $$$a_3=2$$$.
  • Лео меняет местами $$$a_1$$$ $$$(i=1)$$$ и $$$a_2$$$ $$$(j=2)$$$, тогда массив становится $$$[4,1,2]$$$, это стоит $$$j-i=2-1=1$$$.
  • Лео переходит на позицию позади $$$1$$$-го велосипедиста с позиции позади $$$2$$$-го велосипедиста; это стоит $$$a_2=1$$$.
  • Лео меняет местами $$$a_1$$$ $$$(i=1)$$$ и $$$a_2$$$ $$$(j=2)$$$, тогда массив становится $$$[1,4,2]$$$, это стоит $$$j-i=2-1=1$$$.
  • Лео обгоняет $$$1$$$-го велосипедиста; это стоит $$$a_1=1$$$.

Таким образом, общая стоимость составляет $$$1+2+1+1+1+1=7$$$. Можно доказать, что $$$7$$$ является минимальной стоимостью.

Во втором наборе входных данных, чтобы из позиции позади $$$n$$$-го велосипедиста попасть на позицию перед $$$1$$$-м велосипедистом, Лео не нужно менять местами значения ловкости. Общая стоимость составляет $$$1+1+1+1=4$$$.