E. Соперничества
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Ntarsis есть массив $$$a$$$ длины $$$n$$$.

Мощность подотрезка $$$a_l \dots a_r$$$ ($$$1 \leq l \leq r \leq n$$$) определяется следующим образом:

  • Наибольшее значение $$$x$$$, такое что $$$a_l \dots a_r$$$ содержит $$$x$$$, и ни $$$a_1 \dots a_{l-1}$$$, ни $$$a_{r+1} \dots a_n$$$ не содержат $$$x$$$.
  • Если такого $$$x$$$ не существует, мощность равна $$$0$$$.

Массив $$$b$$$ называется соперником для $$$a$$$, если выполняются следующие условия:

  • Длина и $$$a$$$, и $$$b$$$ равна $$$n$$$.
  • Для всех $$$l, r$$$, где $$$1 \leq l \leq r \leq n$$$, мощность $$$a_l \dots a_r$$$ равна мощности $$$b_l \dots b_r$$$.
  • Элементы $$$b$$$ являются положительными числами.

Ntarsis хочет найти соперника $$$b$$$ для $$$a$$$ такого, что сумма $$$b_i$$$ ($$$1 \leq i \leq n$$$) будет максимальной. Помогите ему с этой задачей!

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

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

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

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

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

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ — допустимого соперника для $$$a$$$ такого, что сумма $$$b_1 + b_2 + \cdots + b_n$$$ будет максимальной.

Если существует несколько соперников с максимальной суммой, выведите любого из них.

Пример
Входные данные
7
5
1 4 1 3 3
5
1 4 1 8 8
5
2 1 1 1 2
8
3 2 3 5 2 2 5 3
8
1 1 1 1 4 3 3 3
10
1 9 5 9 8 1 5 8 9 1
16
1 1 1 1 5 5 5 5 9 9 9 9 7 7 7 7
Выходные данные
2 4 2 3 3
3 4 3 8 8
2 1 2 1 2
4 2 4 5 5 2 5 4
1 2 2 1 4 3 2 3
7 9 5 9 8 9 5 8 9 7
1 8 8 1 5 8 8 5 9 9 9 9 7 8 8 7
Примечание

Для первого набора одним из соперников с максимальной суммой является $$$[2, 4, 2, 3, 3]$$$.

Можно показать, что $$$[2, 4, 2, 3, 3]$$$ является соперником для $$$[1, 4, 1, 3, 3]$$$.

Ниже перечислены все возможные подмассивы $$$a$$$ и $$$b$$$ и их соответствующие мощности:

  • Мощность $$$a[1:1] = [1] = 0$$$, мощность $$$b[1:1] = [2] = 0$$$.
  • Мощность $$$a[1:2] = [1, 4] = 4$$$, мощность $$$b[1:2] = [2, 4] = 4$$$.
  • Мощность $$$a[1:3] = [1, 4, 1] = 4$$$, мощность $$$b[1:3] = [2, 4, 2] = 4$$$.
  • Мощность $$$a[1:4] = [1, 4, 1, 3] = 4$$$, мощность $$$b[1:4] = [2, 4, 2, 3] = 4$$$.
  • Мощность $$$a[1:5] = [1, 4, 1, 3, 3] = 4$$$, мощность $$$b[1:5] = [2, 4, 2, 3, 3] = 4$$$.
  • Мощность $$$a[2:2] = [4] = 4$$$, мощность $$$b[2:2] = [4] = 4$$$.
  • Мощность $$$a[2:3] = [4, 1] = 4$$$, мощность $$$b[2:3] = [4, 2] = 4$$$.
  • Мощность $$$a[2:4] = [4, 1, 3] = 4$$$, мощность $$$b[2:4] = [4, 2, 3] = 4$$$.
  • Мощность $$$a[2:5] = [4, 1, 3, 3] = 4$$$, мощность $$$b[2:5] = [4, 2, 3, 3] = 4$$$.
  • Мощность $$$a[3:3] = [1] = 0$$$, мощность $$$b[3:3] = [2] = 0$$$.
  • Мощность $$$a[3:4] = [1, 3] = 0$$$, мощность $$$b[3:4] = [2, 3] = 0$$$.
  • Мощность $$$a[3:5] = [1, 3, 3] = 3$$$, мощность $$$b[3:5] = [2, 3, 3] = 3$$$.
  • Мощность $$$a[4:4] = [3] = 0$$$, мощность $$$b[4:4] = [3] = 0$$$.
  • Мощность $$$a[4:5] = [3, 3] = 3$$$, мощность $$$b[4:5] = [3, 3] = 3$$$.
  • Мощность $$$a[5:5] = [3] = 0$$$, мощность $$$b[5:5] = [3] = 0$$$.

Можно показать, что не существует соперника с большей суммой, чем $$$2 + 4 + 2 + 3 + 3 = 14$$$.