C. Лексикографически наибольший
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Стека есть массив $$$a$$$ длины $$$n$$$. У него также есть пустое множество $$$S$$$. Заметим, что $$$S$$$ не является мультимножеством.

Он выполнит следующую трехшаговую операцию ровно $$$n$$$ раз:

  1. Выбрать индекс $$$i$$$ такой, что $$$1 \leq i \leq |a|$$$.
  2. Вставить$$$^\dagger$$$ $$$a_i + i$$$ в $$$S$$$.
  3. Удалить $$$a_i$$$ из $$$a$$$. Обратите внимание, что индексы всех элементов справа от $$$a_i$$$ уменьшаются на $$$1$$$.

Обратите внимание, что после $$$n$$$ операций массив $$$a$$$ станет пустым.

После Стек построит новый массив $$$b$$$, который является $$$S$$$, отсортированным в порядке убывания. Формально, $$$b$$$ — это массив длины $$$|S|$$$, где $$$b_i$$$ — $$$i$$$-й наибольший элемент $$$S$$$ для всех $$$1 \leq i \leq |S|$$$.

Найдите лексикографически наибольший$$$^\ddagger$$$ массив $$$b$$$, который может получить Стек.

$$$^\dagger$$$ Множество может содержать только уникальные элементы. Вставка элемента, который уже присутствует в множестве, не изменит множество.

$$$^\ddagger$$$ Массив $$$p$$$ лексикографически больше массива $$$q$$$ тогда и только тогда, когда выполняется одно из следующих условий:

  • $$$q$$$ является префиксом $$$p$$$, но $$$p \ne q$$$; или
  • в первой позиции, где $$$p$$$ и $$$q$$$ различаются, массив $$$p$$$ имеет больший элемент, чем соответствующий элемент в $$$q$$$.

Заметим, что $$$[3,1,4,1,5]$$$ лексикографически больше, чем $$$[3,1,3]$$$, $$$[\,]$$$ и $$$[3,1,4,1]$$$, но не больше $$$[3,1,4,1,5,9]$$$, $$$[3,1,4,1,5]$$$ и $$$[4]$$$.

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

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

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

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

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите лексикографически наибольшее значение $$$b$$$.

Пример
Входные данные
3
2
2 1
5
1 100 1000 1000000 1000000000
3
6 4 8
Выходные данные
3 2 
1000000005 1000004 1003 102 2 
11 7 6
Примечание

В первом наборе входных данных выберите $$$i=1$$$ в первой операции, вставьте $$$a_1 + 1 = 3$$$ в $$$S$$$ и удалите $$$a_1$$$ из $$$a$$$. После первой операции массив $$$a$$$ станет $$$a=[1]$$$. Во второй операции снова выберите $$$i=1$$$ и вставьте $$$a_1 + 1 = 2$$$ в $$$S$$$. Таким образом, $$$S=\{2, 3\}$$$, и $$$b = [3, 2]$$$.

Обратите внимание, что если в первой операции выбрать $$$i=2$$$, а во второй выбрать $$$i=1$$$, то $$$S=\{3\}$$$, так как $$$3$$$ будет вставлено дважды, в результате чего $$$b=[3]$$$.

Поскольку $$$[3,2]$$$ лексикографически больше $$$[3]$$$, то в первой операции следует выбрать $$$i=1$$$.

Во втором примере в каждой операции нужно выбирать последний элемент.