У Фермера Джона есть перестановка \(p\) длины \(N\) (\(2 \leq N \leq 10^5)\),
содержащая каждое положительное целое от \(1\) до \(N\) ровно один раз.
Однако Фермер Нхой прокрался в амбар ФД и испортил \(p\). Чтобы не быть
совсем плохим, ФН написал несколько советов, которые помогут ФД
восстановить \(p\). Пока в \(p\) было более одного элемента, ФН делал следующее:
Пусть оставшиеся элементы \(p\) есть
\(p'_1, p'_2, \dots , p'_n\),
- Если \(p'_1 > p'_n\), он записывал \(p'_2\) и удалял \(p'_1\)
из перестановки.
- Иначе, он выписывал \(p'_{n-1}\) и удалял \(p'_n\) из перестановки.
В конце у ФН получились выписанные \(N - 1\) целых чисел
\(h_1, h_2, \dots, h_{N-1}\), в указанном порядке.
По заданным числам \(h\) ФД просит у Вас помощи реконструировать лексикографически
минимальную перестановку \(p\), соответствующую алгоритму ФН или определить,
что ФН сделал ошибку.
Напомним, что если Вам даны две перестановки \(p\) и \(p'\), то
\(p\) лексикографически меньше чем \(p'\), если \(p_i < p'_i\) в первой позиции,
\(i\), где они различаются.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Каждый ввод состоит из
\(T\) независимых подтестов (
\(1\le T\le 10\)).
Каждый подтест описывается следующим образом:
Первая строка содержит число \(N\).
Вторая строка содержит \(N - 1\) целых чисел \(h_1, h_2, \dots, h_{N-1}\)
(\(1\le h_i\le N\)).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите
\(T\) строк, по одной на каждый подтест.
Если существует такая перестановка \(p\) из чисел \(1\dots N\), соответствующая
\(h\), выведите лексикографически минимальную такую перестановку \(p\).
Если такой перестановки \(p\) не существует, выведите \(-1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2
1
2
2
4
1 1 1
4
2 1 1
4
3 2 1
|
1 2
-1
-1
3 1 2 4
1 2 3 4
|