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

Поликарп выписал на доску массив $$$p$$$ длины $$$n$$$, который являлся перестановкой чисел от $$$1$$$ до $$$n$$$. Иными словами, в массиве $$$p$$$ каждое число от $$$1$$$ до $$$n$$$ встречалось ровно один раз.

Также он подготовил массив-ответ $$$a$$$, который изначально пустой (то есть имеет длину $$$0$$$).

После этого он сделал ровно $$$n$$$ действий. Каждое действие выглядело так:

  • Посмотрим на самый левый и самый правый элементы $$$p$$$, выберем минимальный из них.
  • Если выбранный элемент крайний левый в $$$p$$$, то допишем его слева в массив $$$a$$$; в противном случае, если выбранный элемент крайний правый в $$$p$$$, то допишем его справа в массив $$$a$$$.
  • Выбранный элемент удаляется из $$$p$$$.

Отметим, что на последнем действии массив $$$p$$$ имеет длину $$$1$$$ и его минимальный элемент является одновременно и крайним левым и крайним правым. В этом случае Поликарп может сам выбрать, какую роль играет минимальный элемент. Иными словами, этот элемент можно дописать в $$$a$$$ как слева, так и справа (на усмотрение Поликарпа).

Рассмотрим пример. Пусть $$$n=4$$$, $$$p=[3, 1, 4, 2]$$$. Изначально $$$a=[]$$$. Тогда:

  • Во время первого действия минимум справа (это значение $$$2$$$), то есть после этого действия $$$p=[3,1,4]$$$, а массив $$$a=[2]$$$ (в него мы дописали значение $$$2$$$ справа).
  • Во время второго действия минимум слева (это значение $$$3$$$), то есть после этого действия $$$p=[1,4]$$$, а массив $$$a=[3,2]$$$ (в него мы дописали значение $$$3$$$ слева).
  • Во время третьего действия минимум слева (это значение $$$1$$$), то есть после этого действия $$$p=[4]$$$, а массив $$$a=[1,3,2]$$$ (в него мы дописали значение $$$1$$$ слева).
  • Во время четвертого действия минимум и слева и справа (это значение $$$4$$$). Допустим Поликарп выбрал правый вариант. После этого действия $$$p=[]$$$, а массив $$$a=[1,3,2,4]$$$ (в него мы дописали значение $$$4$$$ справа).

Таким образом, возможным значением массива $$$a$$$ после $$$n$$$ действий может быть такое $$$a=[1,3,2,4]$$$.

Вам задано итоговое значение массива $$$a$$$. Найдите любое возможное начальное значение массива $$$p$$$, которое может привести к заданному массиву $$$a$$$, или определите, что решения не существует.

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

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

Каждый набор входных данных состоит из двух строк. В первой из них записано целое число $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — длина массива $$$a$$$. Во второй записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы массива $$$a$$$. Все элементы массива $$$a$$$ — различные числа.

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

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

Выведите $$$t$$$ строк, каждая из строк должна содержать ответ на соответствующий набор входных данных: числа $$$p_1, p_2, \dots, p_n$$$ — любое из возможных начальных значений массива $$$p$$$, которое приведёт к заданному во входных данных значению массива $$$a$$$. Все элементы $$$p$$$ — различные целые числа от $$$1$$$ до $$$n$$$. Таким образом, если существует несколько решений, то выведите любое. Если решения не существует, то в строку выведите -1.

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

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

Во втором наборе входных данных примера $$$n=1$$$. Таким образом, существует единственная перестановка, которая может быть ответом: $$$p=[1]$$$. В самом деле, это ответ на этот набор входных данных.

В третьем наборе входных данных примера какую бы вы перестановку не взяли в качестве $$$p$$$, после применения $$$n$$$ действий результат будет отличен от $$$a=[1, 3, 5, 4, 2]$$$.