C. Монстры (сложная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. В этой версии задачи ответ нужно вычислить для каждого префикса массива монстров.

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

Вы можете использовать заклинания двух типов:

  1. Нанести $$$1$$$ единицу урона любому живому монстру на ваш выбор.
  2. Нанести $$$1$$$ единицу урона всем живым монстрам. Если хотя бы один монстр умирает (оказывается с $$$0$$$ единицами здоровья) в результате этого действия — повторить его (и продолжать повторять, пока хотя бы один монстр умирает после каждого применения).

При нанесении $$$1$$$ единицы урона здоровье монстра уменьшается на $$$1$$$.

Заклинания типа 1 могут быть использованы сколько угодно раз, а заклинание типа 2 — не более одного раза за игру.

Для каждого $$$k = 1, 2, \ldots, n$$$ ответьте на следующий вопрос. Пусть в игре присутствуют только первые $$$k$$$ монстров, с номерами $$$1, 2, \ldots, k$$$. Какое наименьшее число раз вам нужно применить заклинания типа 1, чтобы убить всех $$$k$$$ монстров?

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

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

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — число единиц здоровья у монстров.

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

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел. $$$k$$$-е из этих чисел должно быть равно наименьшему числу раз, которое нужно применить заклинания типа 1, чтобы убить всех $$$k$$$ монстров, если в игре присутствуют только монстры с номерами $$$1, 2, \ldots, k$$$.

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

В первом наборе входных данных при $$$k = n$$$ начальные значения здоровья у монстров равны $$$[3, 1, 2]$$$. Достаточно применить заклинание типа 2:

  • Здоровья монстров становятся равны $$$[2, 0, 1]$$$. Так как монстр номер $$$2$$$ умер, заклинание повторяется.
  • Здоровья монстров становятся равны $$$[1, 0, 0]$$$. Так как монстр номер $$$3$$$ умер, заклинание повторяется.
  • Здоровья монстров становятся равны $$$[0, 0, 0]$$$. Так как монстр номер $$$1$$$ умер, заклинание повторяется.
  • Здоровья монстров становятся равны $$$[0, 0, 0]$$$.

Так как можно обойтись вообще без заклинаний типа 1, ответ равен $$$0$$$.

Во втором наборе входных данных при $$$k = n$$$ начальные значения здоровья у монстров равны $$$[4, 1, 5, 4, 1, 1]$$$. Одной из оптимальных является следующая последовательность действий:

  • Используя заклинание типа 1, нанести $$$1$$$ единицу урона монстру номер $$$1$$$. Здоровья монстров становятся равны $$$[3, 1, 5, 4, 1, 1]$$$.
  • Используя заклинание типа 1, нанести $$$1$$$ единицу урона монстру номер $$$4$$$. Здоровья монстров становятся равны $$$[3, 1, 5, 3, 1, 1]$$$.
  • Используя заклинание типа 1, снова нанести $$$1$$$ единицу урона монстру номер $$$4$$$. Здоровья монстров становятся равны $$$[3, 1, 5, 2, 1, 1]$$$.
  • Использовать заклинание типа 2:
    • Здоровья монстров становятся равны $$$[2, 0, 4, 1, 0, 0]$$$. Так как монстры номер $$$2$$$, $$$5$$$ и $$$6$$$ умерли, заклинание повторяется.
    • Здоровья монстров становятся равны $$$[1, 0, 3, 0, 0, 0]$$$. Так как монстр номер $$$4$$$ умер, заклинание повторяется.
    • Здоровья монстров становятся равны $$$[0, 0, 2, 0, 0, 0]$$$. Так как монстр номер $$$1$$$ умер, заклинание повторяется.
    • Здоровья монстров становятся равны $$$[0, 0, 1, 0, 0, 0]$$$.
  • Используя заклинание типа 1, нанести $$$1$$$ единицу урона монстру номер $$$3$$$. Здоровья монстров становятся равны $$$[0, 0, 0, 0, 0, 0]$$$.

Всего заклинания типа 1 были применены $$$4$$$ раза. Можно показать, что это наименьшее возможное число.