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

Перестановка — это последовательность из $$$n$$$ целых чисел от $$$1$$$ до $$$n$$$, в которой все числа встречаются ровно по одному разу. Например, $$$[1]$$$, $$$[3, 5, 2, 1, 4]$$$, $$$[1, 3, 2]$$$ — перестановки, а $$$[2, 3, 2]$$$, $$$[4, 3, 1]$$$, $$$[0]$$$ — нет.

Поликарпу подарили перестановку $$$p$$$ чисел от $$$1$$$ до $$$n$$$. Однако, когда Поликарп пришёл домой, он заметил, что в кармане перестановка $$$p$$$ превратилась в массив $$$q$$$ согласно следующему правилу:

  • $$$q_i = \max(p_1, p_2, \ldots, p_i)$$$.

Теперь Поликарпу стало интересно: какую лексикографически минимальную и лексикографически максимальную перестановки ему могли подарить.

Массив $$$a$$$ длины $$$n$$$ лексикографически меньше массива $$$b$$$ длины $$$n$$$, если существует индекс $$$i$$$ ($$$1 \le i \le n$$$), такой что первые $$$i-1$$$ элементов у массивов $$$a$$$ и $$$b$$$ совпадают, а $$$i$$$-й элемент у массива $$$a$$$ меньше, чем $$$i$$$-й элемент у массива $$$b$$$. Например массив $$$a=[1, 3, 2, 3]$$$ лексикографически меньше массива $$$b=[1, 3, 4, 2]$$$.

Например, если $$$n=7$$$ и $$$p=[3, 2, 4, 1, 7, 5, 6]$$$, тогда $$$q=[3, 3, 4, 4, 7, 7, 7]$$$ и следующие перестановки могли быть в качестве $$$p$$$ изначально:

  • $$$[3, 1, 4, 2, 7, 5, 6]$$$ (лексикографически минимальная перестановка);
  • $$$[3, 1, 4, 2, 7, 6, 5]$$$;
  • $$$[3, 2, 4, 1, 7, 5, 6]$$$;
  • $$$[3, 2, 4, 1, 7, 6, 5]$$$ (лексикографически максимальная перестановка).

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

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$q_1, q_2, \ldots, q_n$$$ ($$$1 \le q_i \le n$$$).

Гарантируется, что массив $$$q$$$ был получен применением правила из условия к какой-то перестановке $$$p$$$.

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

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

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

  • в первой строке выведите $$$n$$$ целых чисел — лексикографически минимальную перестановку, которая могла быть подарена Поликарпу изначально;
  • во второй строке выведите $$$n$$$ целых чисел — лексикографически максимальную перестановку, которая могла быть подарена Поликарпу изначально.
Пример
Входные данные
4
7
3 3 4 4 7 7 7
4
1 2 3 4
7
3 4 5 5 5 7 7
1
1
Выходные данные
3 1 4 2 7 5 6 
3 2 4 1 7 6 5 
1 2 3 4 
1 2 3 4 
3 4 5 1 2 7 6 
3 4 5 2 1 7 6 
1 
1