Поликарп выписал на доску массив \(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\) строк, каждая из строк должна содержать ответ на соответствующий набор входных данных: числа \(p_1, p_2, \dots, p_n\) — любое из возможных начальных значений массива \(p\), которое приведёт к заданному во входных данных значению массива \(a\). Все элементы \(p\) — различные целые числа от \(1\) до \(n\). Таким образом, если существует несколько решений, то выведите любое. Если решения не существует, то в строку выведите -1.
Примечание
Первый набор входных данных примера разобран в основной части условия. Возможны и другие правильные ответы на этот набор входных данных.
Во втором наборе входных данных примера \(n=1\). Таким образом, существует единственная перестановка, которая может быть ответом: \(p=[1]\). В самом деле, это ответ на этот набор входных данных.
В третьем наборе входных данных примера какую бы вы перестановку не взяли в качестве \(p\), после применения \(n\) действий результат будет отличен от \(a=[1, 3, 5, 4, 2]\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|