C. Кот, Лиса и Двойной максимум
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лиса любит перестановки! Она придумала следующую задачу, и предложила Коту её решить:

Вам дано четное целое положительное число $$$n$$$ и перестановка$$$^\dagger$$$ $$$p$$$ длины $$$n$$$.

Счет другой перестановки $$$q$$$ длины $$$n$$$ определим как количество локальных максимумов в массиве $$$a$$$ длины $$$n$$$, где $$$a_i = p_i + q_i$$$ для всех индексов $$$i$$$ ($$$1 \le i \le n$$$). Другими словами, счет $$$q$$$ — это количество $$$i$$$ таких, что $$$1 < i < n$$$ (обратите внимание на строгие неравенства), $$$a_{i-1} < a_i$$$ и $$$a_i > a_{i+1}$$$ (еще раз обратите внимание на строгие неравенства).

Найдите перестановку $$$q$$$, которая достигает максимального счета при заданных $$$n$$$ и $$$p$$$. Если таких перестановок несколько, вы можете вывести любую из них.

$$$^\dagger$$$ Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ — не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$). Гарантируется, что $$$p$$$ действительно является перестановкой длины $$$n$$$.

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

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

Для каждого набора входных данных выведите одну строку, содержащую любую перестановку чисел длины $$$n$$$ (массив $$$q$$$) такую, что счёт $$$q$$$ максимален при заданных ограничениях.

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

В первом примере $$$a = [3, 6, 4, 7]$$$. Массив имеет только один локальный максимум (на второй позиции), поэтому счет выбранной перестановки $$$q$$$ равен $$$1$$$. Можно доказать, что этот счет оптимален при заданных ограничениях.

В последнем примере полученный массив $$$a = [6, 6, 12, 7, 14, 7, 14, 6]$$$ имеет $$$3$$$ максимума — на третьей, пятой и седьмой позициях.