B. Коробка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перестановка $$$p$$$  — это последовательность целых чисел $$$p=[p_1, p_2, \dots, p_n]$$$, которая состоит из $$$n$$$ различных положительных целых чисел от $$$1$$$ до $$$n$$$. Например, следующие последовательности являются перестановками  — $$$[3, 4, 1, 2]$$$, $$$[1]$$$, $$$[1, 2]$$$. Следующие последовательности не являются перестановками  — $$$[0]$$$, $$$[1, 2, 1]$$$, $$$[2, 3]$$$, $$$[0, 1, 2]$$$.

Важный ключ спрятан в закрытой коробке, которую вам нужно открыть. Чтобы открыть коробку вам нужно ввести секретный ключ. Секретный ключ это перестановка $$$p$$$ длины $$$n$$$.

Эту перестановку вы не знаете, вы знаете только массив $$$q$$$ префиксных максимумов этой перестановки. Формально:

  • $$$q_1=p_1$$$,
  • $$$q_2=\max(p_1, p_2)$$$,
  • $$$q_3=\max(p_1, p_2,p_3)$$$,
  • ...
  • $$$q_n=\max(p_1, p_2,\dots,p_n)$$$.

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

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

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

В первой строке описания набора входных данных записано одно целое число $$$n$$$ $$$(1 \le n \le 10^{5})$$$ — количество элементов в перестановке-секретном коде $$$p$$$.

Во второй строке описания набора входных данных записаны $$$n$$$ целых чисел, $$$q_1, q_2, \dots, q_n$$$ $$$(1 \le q_i \le n)$$$: элементы массива $$$q$$$ для данной перестановки. Гарантируется, что $$$q_i \le q_{i+1}$$$ для всех $$$i$$$ ($$$1 \le i < n$$$).

Сумма всех значений $$$n$$$ по всем наборам входных данных в тесте не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите:

  • Если невозможно найти подходящую перестановку $$$p$$$, выведите «-1» (без кавычек).
  • Иначе, выведите $$$n$$$ различных целых чисел, $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$). Если для набора входных данных есть несколько возможных ответов, вы можете вывести любой.
Пример
Входные данные
4
5
1 3 4 5 5
4
1 1 3 4
2
2 2
1
1
Выходные данные
1 3 4 5 2 
-1
2 1 
1
Примечание

В первом наборе входных данных примера $$$[1,3,4,5,2]$$$ это единственный возможный ответ.

  • $$$q_{1} = p_{1} = 1$$$;
  • $$$q_{2} = \max(p_{1}, p_{2}) = 3$$$;
  • $$$q_{3} = \max(p_{1}, p_{2}, p_{3}) = 4$$$;
  • $$$q_{4} = \max(p_{1}, p_{2}, p_{3}, p_{4}) = 5$$$;
  • $$$q_{5} = \max(p_{1}, p_{2}, p_{3}, p_{4}, p_{5}) = 5$$$.

Можно доказать, что для второго набора входных данных примера не существует ответа.