B. Выравнивание тортика
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса готовит тортик к своей вечеринке. Однако она торопится, поэтому глазурь на торте лежит неровно. Чтобы быстро решить эту проблему, Алиса поставит нож на некоторой целой высоте и затем проведёт им по глазури слева направо, чтобы выровнять её.

Формально, пусть $$$a_i$$$ — высота глазури на $$$i$$$-й позиции. Предположим, что Алиса ставит нож на некоторой целой высоте $$$h$$$. Если высота глазури на позиции $$$i$$$ больше $$$h$$$, то лишняя глазурь будет сдвинута на позицию $$$i + 1$$$. Лишняя глазурь на позиции $$$n$$$ будет полностью сдвинута с торта.

Алиса и её друзья очень любят глазурь на торте. Поскольку Алиса может решить подать только некоторый префикс торта вместо всего торта, помогите ей найти для каждого $$$i = 1, 2, \ldots, n$$$ максимальную высоту, которой может достигать глазурь, чтобы при этом высота глазури на первых $$$i$$$ позициях была одинаковой.

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

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

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

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

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

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

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

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

Пояснение к первому набору входных данных следующее:

Когда $$$i = 1$$$, Алису интересует торт, представленный массивом $$$[4]$$$. Поскольку у такого торта все высоты уже равны, максимальная высота глазури равна $$$4$$$.

Когда $$$i = 2$$$, Алису интересует торт, представленный массивом $$$[4, 2]$$$. Если Алиса поставит нож на высоте $$$4$$$, то получившийся торт будет иметь высоту глазури $$$[4, 2]$$$, и торт не будет выровнен. Однако если Алиса поставит нож на высоте $$$3$$$, одна единица глазури будет сдвинута из первой позиции во вторую, и в результате высота глазури станет $$$[3, 3]$$$, что является выровненным состоянием. Поэтому максимальная высота глазури при равных высотах равна $$$3$$$.

Когда $$$i = 3$$$, если Алиса поставит нож на высоте $$$4$$$, то получившийся уровень глазури будет $$$[4, 2, 3]$$$. Однако если Алиса поставит нож на высоте $$$3$$$, то получившийся уровень глазури будет $$$[3, 3, 3]$$$. Поэтому максимальная высота глазури для выровненного торта равна $$$3$$$.