Для строки $s$ длины $n$ определим $p_j = x$, если $s[x \dots j]$ является минимальным суффиксом строки $s[1 \dots j]$ для всех $j = 1, \dots, n$. (Суффикс является минимальным суффиксом строки, если он лексикографически меньше или равен любому другому суффиксу этой строки.)

Вам необходимо восстановить $s$ по заданным $p_1, \dots, p_n$. Если существует несколько решений, найдите лексикографически наименьшее из них.

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

Первая строка содержит единственное целое число $T$ ($1 \le T \le 10^5$), представляющее количество тестовых случаев.

Для каждого тестового случая первая строка содержит единственное целое число $n$ ($1 \le n \le 3 \times 10^6$), представляющее длину строки $s$. Следующая строка содержит $n$ целых чисел $p_1, \dots, p_n$ ($1 \le p_i \le i$ для всех $1 \le i \le n$).

Гарантируется, что сумма $n$ по всем тестовым случаям не превышает $3 \times 10^6$.

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

Для каждого тестового случая выведите одну строку. Если решения не существует, выведите $-1$. В противном случае выведите лексикографически наименьшую строку $s$. Символы строки $s$ представлены положительными целыми числами. Меньшие целые числа соответствуют меньшим символам в лексикографическом порядке.

Примеры

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

6
3
1 1 1
3
1 1 2
3
1 1 3
3
1 2 1
3
1 2 2
3
1 2 3

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

1 2 2
-1
1 2 1
1 1 2
2 1 2
1 1 1

Примечание

Так как объем входных и выходных данных может быть очень большим, рекомендуется использовать быстрые методы ввода/вывода.