A permutation is a sequence of $n$ integers from $1$ to $n$, in which all numbers occur exactly once. For example, $[1]$, $[3, 5, 2, 1, 4]$, $[1, 3, 2]$ are permutations, and $[2, 3, 2]$, $[4, 3, 1]$, $[0]$ are not.

Polycarp was presented with a permutation $p$ of numbers from $1$ to $n$. However, when Polycarp came home, he noticed that in his pocket, the permutation $p$ had turned into an array $q$ according to the following rule:

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

Now Polycarp wondered what lexicographically minimal and lexicographically maximal permutations could be presented to him.

An array $a$ of length $n$ is lexicographically smaller than an array $b$ of length $n$ if there is an index $i$ ($1 \le i \le n$) such that the first $i-1$ elements of arrays $a$ and $b$ are the same, and the $i$-th element of the array $a$ is less than the $i$-th element of the array $b$. For example, the array $a=[1, 3, 2, 3]$ is lexicographically smaller than the array $b=[1, 3, 4, 2]$.

For example, if $n=7$ and $p=[3, 2, 4, 1, 7, 5, 6]$, then $q=[3, 3, 4, 4, 7, 7, 7]$ and the following permutations could have been as $p$ initially:

$[3, 1, 4, 2, 7, 5, 6]$ (lexicographically minimal permutation);

$[3, 1, 4, 2, 7, 6, 5]$;

$[3, 2, 4, 1, 7, 5, 6]$;

$[3, 2, 4, 1, 7, 6, 5]$ (lexicographically maximum permutation).

For a given array $q$, find the lexicographically minimal and lexicographically maximal permutations that could have been originally presented to Polycarp.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10^4$). Then $t$ test cases follow.

The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$).

The second line of each test case contains $n$ integers $q_1, q_2, \ldots, q_n$ ($1 \le q_i \le n$).

It is guaranteed that the array $q$ was obtained by applying the rule from the statement to some permutation $p$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, output two lines:

on the first line output $n$ integers — lexicographically minimal permutation that could have been originally presented to Polycarp;

on the second line print $n$ integers — lexicographically maximal permutation that could have been originally presented to Polycarp;


-----Examples-----

Input
4
7
3 3 4 4 7 7 7
4
1 2 3 4
7
3 4 5 5 5 7 7
1
1
Output
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


-----Note-----

None

Difficulty: MEDIUM
Tags: Implementation

Constructive algorithms

Starter code:

Solutions:
from collections import deque
t = int(input())
for i in range(t):
	och = deque()
	n = int(input())
	d = list(map(int, input().split()))
	pos = 0
	ans = []
	for j in d:
		if j > pos:
			ans.append(j)
			for k in range(pos + 1, j):
				och.append(k)
		else:
			ans.append(och.popleft())
		pos = j
	print(*ans)
	pos = 0
	ans = []
	for j in d:
		if j > pos:
			ans.append(j)
			for k in range(pos + 1, j):
				och.append(k)
		else:
			ans.append(och.pop())
		pos = j
	print(*ans)


from __future__ import print_function
import sys
import traceback
from bisect import bisect_left, bisect_right, insort
from itertools import chain, repeat, starmap
from math import log
from operator import add, eq, ne, gt, ge, lt, le, iadd
from textwrap import dedent
try:
	from collections.abc import Sequence, MutableSequence
except ImportError:
	from collections import Sequence, MutableSequence
from functools import wraps
from sys import hexversion
if hexversion < 50331648:
	from itertools import imap as map
	from itertools import izip as zip
	try:
		from thread import get_ident
	except ImportError:
		from dummy_thread import get_ident
else:
	from functools import reduce
	try:
		from _thread import get_ident
	except ImportError:
		from _dummy_thread import get_ident

def recursive_repr(fillvalue='...'):

	def decorating_function(user_function):
		repr_running = set()

		@wraps(user_function)
		def wrapper(self):
			key = (id(self), get_ident())
			if key in repr_running:
				return fillvalue
			repr_running.add(key)
			try:
				result = user_function(self)
			finally:
				repr_running.discard(key)
			return result
		return wrapper
	return decorating_function

class SortedList(MutableSequence):
	DEFAULT_LOAD_FACTOR = 1000

	def __init__(self, iterable=None, key=None):
		assert key is None
		self._len = 0
		self._load = self.DEFAULT_LOAD_FACTOR
		self._lists = []
		self._maxes = []
		self._index = []
		self._offset = 0
		if iterable is not None:
			self._update(iterable)

	def __new__(cls, iterable=None, key=None):
		if key is None:
			return object.__new__(cls)
		elif cls is SortedList:
			return object.__new__(SortedKeyList)
		else:
			raise TypeError('inherit SortedKeyList for key argument')

	@property
	def key(self):
		return None

	def _reset(self, load):
		values = reduce(iadd, self._lists, [])
		self._clear()
		self._load = load
		self._update(values)

	def clear(self):
		self._len = 0
		del self._lists[:]
		del self._maxes[:]
		del self._index[:]
		self._offset = 0
	_clear = clear

	def add(self, value):
		_lists = self._lists
		_maxes = self._maxes
		if _maxes:
			pos = bisect_right(_maxes, value)
			if pos == len(_maxes):
				pos -= 1
				_lists[pos].append(value)
				_maxes[pos] = value
			else:
				insort(_lists[pos], value)
			self._expand(pos)
		else:
			_lists.append([value])
			_maxes.append(value)
		self._len += 1

	def _expand(self, pos):
		_load = self._load
		_lists = self._lists
		_index = self._index
		if len(_lists[pos]) > _load << 1:
			_maxes = self._maxes
			_lists_pos = _lists[pos]
			half = _lists_pos[_load:]
			del _lists_pos[_load:]
			_maxes[pos] = _lists_pos[-1]
			_lists.insert(pos + 1, half)
			_maxes.insert(pos + 1, half[-1])
			del _index[:]
		elif _index:
			child = self._offset + pos
			while child:
				_index[child] += 1
				child = child - 1 >> 1
			_index[0] += 1

	def update(self, iterable):
		_lists = self._lists
		_maxes = self._maxes
		values = sorted(iterable)
		if _maxes:
			if len(values) * 4 >= self._len:
				values.extend(chain.from_iterable(_lists))
				values.sort()
				self._clear()
			else:
				_add = self.add
				for val in values:
					_add(val)
				return
		_load = self._load
		_lists.extend((values[pos:pos + _load] for pos in range(0, len(values), _load)))
		_maxes.extend((sublist[-1] for sublist in _lists))
		self._len = len(values)
		del self._index[:]
	_update = update

	def __contains__(self, value):
		_maxes = self._maxes
		if not _maxes:
			return False
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return False
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		return _lists[pos][idx] == value

	def discard(self, value):
		_maxes = self._maxes
		if not _maxes:
			return
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		if _lists[pos][idx] == value:
			self._delete(pos, idx)

	def remove(self, value):
		_maxes = self._maxes
		if not _maxes:
			raise ValueError('{0!r} not in list'.format(value))
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			raise ValueError('{0!r} not in list'.format(value))
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		if _lists[pos][idx] == value:
			self._delete(pos, idx)
		else:
			raise ValueError('{0!r} not in list'.format(value))

	def _delete(self, pos, idx):
		_lists = self._lists
		_maxes = self._maxes
		_index = self._index
		_lists_pos = _lists[pos]
		del _lists_pos[idx]
		self._len -= 1
		len_lists_pos = len(_lists_pos)
		if len_lists_pos > self._load >> 1:
			_maxes[pos] = _lists_pos[-1]
			if _index:
				child = self._offset + pos
				while child > 0:
					_index[child] -= 1
					child = child - 1 >> 1
				_index[0] -= 1
		elif len(_lists) > 1:
			if not pos:
				pos += 1
			prev = pos - 1
			_lists[prev].extend(_lists[pos])
			_maxes[prev] = _lists[prev][-1]
			del _lists[pos]
			del _maxes[pos]
			del _index[:]
			self._expand(prev)
		elif len_lists_pos:
			_maxes[pos] = _lists_pos[-1]
		else:
			del _lists[pos]
			del _maxes[pos]
			del _index[:]

	def _loc(self, pos, idx):
		if not pos:
			return idx
		_index = self._index
		if not _index:
			self._build_index()
		total = 0
		pos += self._offset
		while pos:
			if not pos & 1:
				total += _index[pos - 1]
			pos = pos - 1 >> 1
		return total + idx

	def _pos(self, idx):
		if idx < 0:
			last_len = len(self._lists[-1])
			if -idx <= last_len:
				return (len(self._lists) - 1, last_len + idx)
			idx += self._len
			if idx < 0:
				raise IndexError('list index out of range')
		elif idx >= self._len:
			raise IndexError('list index out of range')
		if idx < len(self._lists[0]):
			return (0, idx)
		_index = self._index
		if not _index:
			self._build_index()
		pos = 0
		child = 1
		len_index = len(_index)
		while child < len_index:
			index_child = _index[child]
			if idx < index_child:
				pos = child
			else:
				idx -= index_child
				pos = child + 1
			child = (pos << 1) + 1
		return (pos - self._offset, idx)

	def _build_index(self):
		row0 = list(map(len, self._lists))
		if len(row0) == 1:
			self._index[:] = row0
			self._offset = 0
			return
		head = iter(row0)
		tail = iter(head)
		row1 = list(starmap(add, zip(head, tail)))
		if len(row0) & 1:
			row1.append(row0[-1])
		if len(row1) == 1:
			self._index[:] = row1 + row0
			self._offset = 1
			return
		size = 2 ** (int(log(len(row1) - 1, 2)) + 1)
		row1.extend(repeat(0, size - len(row1)))
		tree = [row0, row1]
		while len(tree[-1]) > 1:
			head = iter(tree[-1])
			tail = iter(head)
			row = list(starmap(add, zip(head, tail)))
			tree.append(row)
		reduce(iadd, reversed(tree), self._index)
		self._offset = size * 2 - 1

	def __delitem__(self, index):
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return self._clear()
				elif self._len <= 8 * (stop - start):
					values = self._getitem(slice(None, start))
					if stop < self._len:
						values += self._getitem(slice(stop, None))
					self._clear()
					return self._update(values)
			indices = range(start, stop, step)
			if step > 0:
				indices = reversed(indices)
			(_pos, _delete) = (self._pos, self._delete)
			for index in indices:
				(pos, idx) = _pos(index)
				_delete(pos, idx)
		else:
			(pos, idx) = self._pos(index)
			self._delete(pos, idx)

	def __getitem__(self, index):
		_lists = self._lists
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return reduce(iadd, self._lists, [])
				(start_pos, start_idx) = self._pos(start)
				start_list = _lists[start_pos]
				stop_idx = start_idx + stop - start
				if len(start_list) >= stop_idx:
					return start_list[start_idx:stop_idx]
				if stop == self._len:
					stop_pos = len(_lists) - 1
					stop_idx = len(_lists[stop_pos])
				else:
					(stop_pos, stop_idx) = self._pos(stop)
				prefix = _lists[start_pos][start_idx:]
				middle = _lists[start_pos + 1:stop_pos]
				result = reduce(iadd, middle, prefix)
				result += _lists[stop_pos][:stop_idx]
				return result
			if step == -1 and start > stop:
				result = self._getitem(slice(stop + 1, start + 1))
				result.reverse()
				return result
			indices = range(start, stop, step)
			return list((self._getitem(index) for index in indices))
		else:
			if self._len:
				if index == 0:
					return _lists[0][0]
				elif index == -1:
					return _lists[-1][-1]
			else:
				raise IndexError('list index out of range')
			if 0 <= index < len(_lists[0]):
				return _lists[0][index]
			len_last = len(_lists[-1])
			if -len_last < index < 0:
				return _lists[-1][len_last + index]
			(pos, idx) = self._pos(index)
			return _lists[pos][idx]
	_getitem = __getitem__

	def __setitem__(self, index, value):
		message = 'use ``del sl[index]`` and ``sl.add(value)`` instead'
		raise NotImplementedError(message)

	def __iter__(self):
		return chain.from_iterable(self._lists)

	def __reversed__(self):
		return chain.from_iterable(map(reversed, reversed(self._lists)))

	def reverse(self):
		raise NotImplementedError('use ``reversed(sl)`` instead')

	def islice(self, start=None, stop=None, reverse=False):
		_len = self._len
		if not _len:
			return iter(())
		(start, stop, _) = slice(start, stop).indices(self._len)
		if start >= stop:
			return iter(())
		_pos = self._pos
		(min_pos, min_idx) = _pos(start)
		if stop == _len:
			max_pos = len(self._lists) - 1
			max_idx = len(self._lists[-1])
		else:
			(max_pos, max_idx) = _pos(stop)
		return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)

	def _islice(self, min_pos, min_idx, max_pos, max_idx, reverse):
		_lists = self._lists
		if min_pos > max_pos:
			return iter(())
		if min_pos == max_pos:
			if reverse:
				indices = reversed(range(min_idx, max_idx))
				return map(_lists[min_pos].__getitem__, indices)
			indices = range(min_idx, max_idx)
			return map(_lists[min_pos].__getitem__, indices)
		next_pos = min_pos + 1
		if next_pos == max_pos:
			if reverse:
				min_indices = range(min_idx, len(_lists[min_pos]))
				max_indices = range(max_idx)
				return chain(map(_lists[max_pos].__getitem__, reversed(max_indices)), map(_lists[min_pos].__getitem__, reversed(min_indices)))
			min_indices = range(min_idx, len(_lists[min_pos]))
			max_indices = range(max_idx)
			return chain(map(_lists[min_pos].__getitem__, min_indices), map(_lists[max_pos].__getitem__, max_indices))
		if reverse:
			min_indices = range(min_idx, len(_lists[min_pos]))
			sublist_indices = range(next_pos, max_pos)
			sublists = map(_lists.__getitem__, reversed(sublist_indices))
			max_indices = range(max_idx)
			return chain(map(_lists[max_pos].__getitem__, reversed(max_indices)), chain.from_iterable(map(reversed, sublists)), map(_lists[min_pos].__getitem__, reversed(min_indices)))
		min_indices = range(min_idx, len(_lists[min_pos]))
		sublist_indices = range(next_pos, max_pos)
		sublists = map(_lists.__getitem__, sublist_indices)
		max_indices = range(max_idx)
		return chain(map(_lists[min_pos].__getitem__, min_indices), chain.from_iterable(sublists), map(_lists[max_pos].__getitem__, max_indices))

	def irange(self, minimum=None, maximum=None, inclusive=(True, True), reverse=False):
		_maxes = self._maxes
		if not _maxes:
			return iter(())
		_lists = self._lists
		if minimum is None:
			min_pos = 0
			min_idx = 0
		elif inclusive[0]:
			min_pos = bisect_left(_maxes, minimum)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_left(_lists[min_pos], minimum)
		else:
			min_pos = bisect_right(_maxes, minimum)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_right(_lists[min_pos], minimum)
		if maximum is None:
			max_pos = len(_maxes) - 1
			max_idx = len(_lists[max_pos])
		elif inclusive[1]:
			max_pos = bisect_right(_maxes, maximum)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_lists[max_pos])
			else:
				max_idx = bisect_right(_lists[max_pos], maximum)
		else:
			max_pos = bisect_left(_maxes, maximum)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_lists[max_pos])
			else:
				max_idx = bisect_left(_lists[max_pos], maximum)
		return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)

	def __len__(self):
		return self._len

	def bisect_left(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return self._len
		idx = bisect_left(self._lists[pos], value)
		return self._loc(pos, idx)

	def bisect_right(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_right(_maxes, value)
		if pos == len(_maxes):
			return self._len
		idx = bisect_right(self._lists[pos], value)
		return self._loc(pos, idx)
	bisect = bisect_right
	_bisect_right = bisect_right

	def count(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			return 0
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		pos_right = bisect_right(_maxes, value)
		if pos_right == len(_maxes):
			return self._len - self._loc(pos_left, idx_left)
		idx_right = bisect_right(_lists[pos_right], value)
		if pos_left == pos_right:
			return idx_right - idx_left
		right = self._loc(pos_right, idx_right)
		left = self._loc(pos_left, idx_left)
		return right - left

	def copy(self):
		return self.__class__(self)
	__copy__ = copy

	def append(self, value):
		raise NotImplementedError('use ``sl.add(value)`` instead')

	def extend(self, values):
		raise NotImplementedError('use ``sl.update(values)`` instead')

	def insert(self, index, value):
		raise NotImplementedError('use ``sl.add(value)`` instead')

	def pop(self, index=-1):
		if not self._len:
			raise IndexError('pop index out of range')
		_lists = self._lists
		if index == 0:
			val = _lists[0][0]
			self._delete(0, 0)
			return val
		if index == -1:
			pos = len(_lists) - 1
			loc = len(_lists[pos]) - 1
			val = _lists[pos][loc]
			self._delete(pos, loc)
			return val
		if 0 <= index < len(_lists[0]):
			val = _lists[0][index]
			self._delete(0, index)
			return val
		len_last = len(_lists[-1])
		if -len_last < index < 0:
			pos = len(_lists) - 1
			loc = len_last + index
			val = _lists[pos][loc]
			self._delete(pos, loc)
			return val
		(pos, idx) = self._pos(index)
		val = _lists[pos][idx]
		self._delete(pos, idx)
		return val

	def index(self, value, start=None, stop=None):
		_len = self._len
		if not _len:
			raise ValueError('{0!r} is not in list'.format(value))
		if start is None:
			start = 0
		if start < 0:
			start += _len
		if start < 0:
			start = 0
		if stop is None:
			stop = _len
		if stop < 0:
			stop += _len
		if stop > _len:
			stop = _len
		if stop <= start:
			raise ValueError('{0!r} is not in list'.format(value))
		_maxes = self._maxes
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			raise ValueError('{0!r} is not in list'.format(value))
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		if _lists[pos_left][idx_left] != value:
			raise ValueError('{0!r} is not in list'.format(value))
		stop -= 1
		left = self._loc(pos_left, idx_left)
		if start <= left:
			if left <= stop:
				return left
		else:
			right = self._bisect_right(value) - 1
			if start <= right:
				return start
		raise ValueError('{0!r} is not in list'.format(value))

	def __add__(self, other):
		values = reduce(iadd, self._lists, [])
		values.extend(other)
		return self.__class__(values)
	__radd__ = __add__

	def __iadd__(self, other):
		self._update(other)
		return self

	def __mul__(self, num):
		values = reduce(iadd, self._lists, []) * num
		return self.__class__(values)
	__rmul__ = __mul__

	def __imul__(self, num):
		values = reduce(iadd, self._lists, []) * num
		self._clear()
		self._update(values)
		return self

	def __make_cmp(seq_op, symbol, doc):

		def comparer(self, other):
			if not isinstance(other, Sequence):
				return NotImplemented
			self_len = self._len
			len_other = len(other)
			if self_len != len_other:
				if seq_op is eq:
					return False
				if seq_op is ne:
					return True
			for (alpha, beta) in zip(self, other):
				if alpha != beta:
					return seq_op(alpha, beta)
			return seq_op(self_len, len_other)
		seq_op_name = seq_op.__name__
		comparer.__name__ = '__{0}__'.format(seq_op_name)
		doc_str = 'Return true if and only if sorted list is {0} `other`.\n\n        ``sl.__{1}__(other)`` <==> ``sl {2} other``\n\n        Comparisons use lexicographical order as with sequences.\n\n        Runtime complexity: `O(n)`\n\n        :param other: `other` sequence\n        :return: true if sorted list is {0} `other`\n\n        '
		comparer.__doc__ = dedent(doc_str.format(doc, seq_op_name, symbol))
		return comparer
	__eq__ = __make_cmp(eq, '==', 'equal to')
	__ne__ = __make_cmp(ne, '!=', 'not equal to')
	__lt__ = __make_cmp(lt, '<', 'less than')
	__gt__ = __make_cmp(gt, '>', 'greater than')
	__le__ = __make_cmp(le, '<=', 'less than or equal to')
	__ge__ = __make_cmp(ge, '>=', 'greater than or equal to')
	__make_cmp = staticmethod(__make_cmp)

	def __reduce__(self):
		values = reduce(iadd, self._lists, [])
		return (type(self), (values,))

	@recursive_repr()
	def __repr__(self):
		return '{0}({1!r})'.format(type(self).__name__, list(self))

	def _check(self):
		try:
			assert self._load >= 4
			assert len(self._maxes) == len(self._lists)
			assert self._len == sum((len(sublist) for sublist in self._lists))
			for sublist in self._lists:
				for pos in range(1, len(sublist)):
					assert sublist[pos - 1] <= sublist[pos]
			for pos in range(1, len(self._lists)):
				assert self._lists[pos - 1][-1] <= self._lists[pos][0]
			for pos in range(len(self._maxes)):
				assert self._maxes[pos] == self._lists[pos][-1]
			double = self._load << 1
			assert all((len(sublist) <= double for sublist in self._lists))
			half = self._load >> 1
			for pos in range(0, len(self._lists) - 1):
				assert len(self._lists[pos]) >= half
			if self._index:
				assert self._len == self._index[0]
				assert len(self._index) == self._offset + len(self._lists)
				for pos in range(len(self._lists)):
					leaf = self._index[self._offset + pos]
					assert leaf == len(self._lists[pos])
				for pos in range(self._offset):
					child = (pos << 1) + 1
					if child >= len(self._index):
						assert self._index[pos] == 0
					elif child + 1 == len(self._index):
						assert self._index[pos] == self._index[child]
					else:
						child_sum = self._index[child] + self._index[child + 1]
						assert child_sum == self._index[pos]
		except:
			traceback.print_exc(file=sys.stdout)
			print('len', self._len)
			print('load', self._load)
			print('offset', self._offset)
			print('len_index', len(self._index))
			print('index', self._index)
			print('len_maxes', len(self._maxes))
			print('maxes', self._maxes)
			print('len_lists', len(self._lists))
			print('lists', self._lists)
			raise

def identity(value):
	return value

class SortedKeyList(SortedList):

	def __init__(self, iterable=None, key=identity):
		self._key = key
		self._len = 0
		self._load = self.DEFAULT_LOAD_FACTOR
		self._lists = []
		self._keys = []
		self._maxes = []
		self._index = []
		self._offset = 0
		if iterable is not None:
			self._update(iterable)

	def __new__(cls, iterable=None, key=identity):
		return object.__new__(cls)

	@property
	def key(self):
		return self._key

	def clear(self):
		self._len = 0
		del self._lists[:]
		del self._keys[:]
		del self._maxes[:]
		del self._index[:]
	_clear = clear

	def add(self, value):
		_lists = self._lists
		_keys = self._keys
		_maxes = self._maxes
		key = self._key(value)
		if _maxes:
			pos = bisect_right(_maxes, key)
			if pos == len(_maxes):
				pos -= 1
				_lists[pos].append(value)
				_keys[pos].append(key)
				_maxes[pos] = key
			else:
				idx = bisect_right(_keys[pos], key)
				_lists[pos].insert(idx, value)
				_keys[pos].insert(idx, key)
			self._expand(pos)
		else:
			_lists.append([value])
			_keys.append([key])
			_maxes.append(key)
		self._len += 1

	def _expand(self, pos):
		_lists = self._lists
		_keys = self._keys
		_index = self._index
		if len(_keys[pos]) > self._load << 1:
			_maxes = self._maxes
			_load = self._load
			_lists_pos = _lists[pos]
			_keys_pos = _keys[pos]
			half = _lists_pos[_load:]
			half_keys = _keys_pos[_load:]
			del _lists_pos[_load:]
			del _keys_pos[_load:]
			_maxes[pos] = _keys_pos[-1]
			_lists.insert(pos + 1, half)
			_keys.insert(pos + 1, half_keys)
			_maxes.insert(pos + 1, half_keys[-1])
			del _index[:]
		elif _index:
			child = self._offset + pos
			while child:
				_index[child] += 1
				child = child - 1 >> 1
			_index[0] += 1

	def update(self, iterable):
		_lists = self._lists
		_keys = self._keys
		_maxes = self._maxes
		values = sorted(iterable, key=self._key)
		if _maxes:
			if len(values) * 4 >= self._len:
				values.extend(chain.from_iterable(_lists))
				values.sort(key=self._key)
				self._clear()
			else:
				_add = self.add
				for val in values:
					_add(val)
				return
		_load = self._load
		_lists.extend((values[pos:pos + _load] for pos in range(0, len(values), _load)))
		_keys.extend((list(map(self._key, _list)) for _list in _lists))
		_maxes.extend((sublist[-1] for sublist in _keys))
		self._len = len(values)
		del self._index[:]
	_update = update

	def __contains__(self, value):
		_maxes = self._maxes
		if not _maxes:
			return False
		key = self._key(value)
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			return False
		_lists = self._lists
		_keys = self._keys
		idx = bisect_left(_keys[pos], key)
		len_keys = len(_keys)
		len_sublist = len(_keys[pos])
		while True:
			if _keys[pos][idx] != key:
				return False
			if _lists[pos][idx] == value:
				return True
			idx += 1
			if idx == len_sublist:
				pos += 1
				if pos == len_keys:
					return False
				len_sublist = len(_keys[pos])
				idx = 0

	def discard(self, value):
		_maxes = self._maxes
		if not _maxes:
			return
		key = self._key(value)
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			return
		_lists = self._lists
		_keys = self._keys
		idx = bisect_left(_keys[pos], key)
		len_keys = len(_keys)
		len_sublist = len(_keys[pos])
		while True:
			if _keys[pos][idx] != key:
				return
			if _lists[pos][idx] == value:
				self._delete(pos, idx)
				return
			idx += 1
			if idx == len_sublist:
				pos += 1
				if pos == len_keys:
					return
				len_sublist = len(_keys[pos])
				idx = 0

	def remove(self, value):
		_maxes = self._maxes
		if not _maxes:
			raise ValueError('{0!r} not in list'.format(value))
		key = self._key(value)
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			raise ValueError('{0!r} not in list'.format(value))
		_lists = self._lists
		_keys = self._keys
		idx = bisect_left(_keys[pos], key)
		len_keys = len(_keys)
		len_sublist = len(_keys[pos])
		while True:
			if _keys[pos][idx] != key:
				raise ValueError('{0!r} not in list'.format(value))
			if _lists[pos][idx] == value:
				self._delete(pos, idx)
				return
			idx += 1
			if idx == len_sublist:
				pos += 1
				if pos == len_keys:
					raise ValueError('{0!r} not in list'.format(value))
				len_sublist = len(_keys[pos])
				idx = 0

	def _delete(self, pos, idx):
		_lists = self._lists
		_keys = self._keys
		_maxes = self._maxes
		_index = self._index
		keys_pos = _keys[pos]
		lists_pos = _lists[pos]
		del keys_pos[idx]
		del lists_pos[idx]
		self._len -= 1
		len_keys_pos = len(keys_pos)
		if len_keys_pos > self._load >> 1:
			_maxes[pos] = keys_pos[-1]
			if _index:
				child = self._offset + pos
				while child > 0:
					_index[child] -= 1
					child = child - 1 >> 1
				_index[0] -= 1
		elif len(_keys) > 1:
			if not pos:
				pos += 1
			prev = pos - 1
			_keys[prev].extend(_keys[pos])
			_lists[prev].extend(_lists[pos])
			_maxes[prev] = _keys[prev][-1]
			del _lists[pos]
			del _keys[pos]
			del _maxes[pos]
			del _index[:]
			self._expand(prev)
		elif len_keys_pos:
			_maxes[pos] = keys_pos[-1]
		else:
			del _lists[pos]
			del _keys[pos]
			del _maxes[pos]
			del _index[:]

	def irange(self, minimum=None, maximum=None, inclusive=(True, True), reverse=False):
		min_key = self._key(minimum) if minimum is not None else None
		max_key = self._key(maximum) if maximum is not None else None
		return self._irange_key(min_key=min_key, max_key=max_key, inclusive=inclusive, reverse=reverse)

	def irange_key(self, min_key=None, max_key=None, inclusive=(True, True), reverse=False):
		_maxes = self._maxes
		if not _maxes:
			return iter(())
		_keys = self._keys
		if min_key is None:
			min_pos = 0
			min_idx = 0
		elif inclusive[0]:
			min_pos = bisect_left(_maxes, min_key)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_left(_keys[min_pos], min_key)
		else:
			min_pos = bisect_right(_maxes, min_key)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_right(_keys[min_pos], min_key)
		if max_key is None:
			max_pos = len(_maxes) - 1
			max_idx = len(_keys[max_pos])
		elif inclusive[1]:
			max_pos = bisect_right(_maxes, max_key)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_keys[max_pos])
			else:
				max_idx = bisect_right(_keys[max_pos], max_key)
		else:
			max_pos = bisect_left(_maxes, max_key)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_keys[max_pos])
			else:
				max_idx = bisect_left(_keys[max_pos], max_key)
		return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)
	_irange_key = irange_key

	def bisect_left(self, value):
		return self._bisect_key_left(self._key(value))

	def bisect_right(self, value):
		return self._bisect_key_right(self._key(value))
	bisect = bisect_right

	def bisect_key_left(self, key):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			return self._len
		idx = bisect_left(self._keys[pos], key)
		return self._loc(pos, idx)
	_bisect_key_left = bisect_key_left

	def bisect_key_right(self, key):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_right(_maxes, key)
		if pos == len(_maxes):
			return self._len
		idx = bisect_right(self._keys[pos], key)
		return self._loc(pos, idx)
	bisect_key = bisect_key_right
	_bisect_key_right = bisect_key_right

	def count(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		key = self._key(value)
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			return 0
		_lists = self._lists
		_keys = self._keys
		idx = bisect_left(_keys[pos], key)
		total = 0
		len_keys = len(_keys)
		len_sublist = len(_keys[pos])
		while True:
			if _keys[pos][idx] != key:
				return total
			if _lists[pos][idx] == value:
				total += 1
			idx += 1
			if idx == len_sublist:
				pos += 1
				if pos == len_keys:
					return total
				len_sublist = len(_keys[pos])
				idx = 0

	def copy(self):
		return self.__class__(self, key=self._key)
	__copy__ = copy

	def index(self, value, start=None, stop=None):
		_len = self._len
		if not _len:
			raise ValueError('{0!r} is not in list'.format(value))
		if start is None:
			start = 0
		if start < 0:
			start += _len
		if start < 0:
			start = 0
		if stop is None:
			stop = _len
		if stop < 0:
			stop += _len
		if stop > _len:
			stop = _len
		if stop <= start:
			raise ValueError('{0!r} is not in list'.format(value))
		_maxes = self._maxes
		key = self._key(value)
		pos = bisect_left(_maxes, key)
		if pos == len(_maxes):
			raise ValueError('{0!r} is not in list'.format(value))
		stop -= 1
		_lists = self._lists
		_keys = self._keys
		idx = bisect_left(_keys[pos], key)
		len_keys = len(_keys)
		len_sublist = len(_keys[pos])
		while True:
			if _keys[pos][idx] != key:
				raise ValueError('{0!r} is not in list'.format(value))
			if _lists[pos][idx] == value:
				loc = self._loc(pos, idx)
				if start <= loc <= stop:
					return loc
				elif loc > stop:
					break
			idx += 1
			if idx == len_sublist:
				pos += 1
				if pos == len_keys:
					raise ValueError('{0!r} is not in list'.format(value))
				len_sublist = len(_keys[pos])
				idx = 0
		raise ValueError('{0!r} is not in list'.format(value))

	def __add__(self, other):
		values = reduce(iadd, self._lists, [])
		values.extend(other)
		return self.__class__(values, key=self._key)
	__radd__ = __add__

	def __mul__(self, num):
		values = reduce(iadd, self._lists, []) * num
		return self.__class__(values, key=self._key)

	def __reduce__(self):
		values = reduce(iadd, self._lists, [])
		return (type(self), (values, self.key))

	@recursive_repr()
	def __repr__(self):
		type_name = type(self).__name__
		return '{0}({1!r}, key={2!r})'.format(type_name, list(self), self._key)

	def _check(self):
		try:
			assert self._load >= 4
			assert len(self._maxes) == len(self._lists) == len(self._keys)
			assert self._len == sum((len(sublist) for sublist in self._lists))
			for sublist in self._keys:
				for pos in range(1, len(sublist)):
					assert sublist[pos - 1] <= sublist[pos]
			for pos in range(1, len(self._keys)):
				assert self._keys[pos - 1][-1] <= self._keys[pos][0]
			for (val_sublist, key_sublist) in zip(self._lists, self._keys):
				assert len(val_sublist) == len(key_sublist)
				for (val, key) in zip(val_sublist, key_sublist):
					assert self._key(val) == key
			for pos in range(len(self._maxes)):
				assert self._maxes[pos] == self._keys[pos][-1]
			double = self._load << 1
			assert all((len(sublist) <= double for sublist in self._lists))
			half = self._load >> 1
			for pos in range(0, len(self._lists) - 1):
				assert len(self._lists[pos]) >= half
			if self._index:
				assert self._len == self._index[0]
				assert len(self._index) == self._offset + len(self._lists)
				for pos in range(len(self._lists)):
					leaf = self._index[self._offset + pos]
					assert leaf == len(self._lists[pos])
				for pos in range(self._offset):
					child = (pos << 1) + 1
					if child >= len(self._index):
						assert self._index[pos] == 0
					elif child + 1 == len(self._index):
						assert self._index[pos] == self._index[child]
					else:
						child_sum = self._index[child] + self._index[child + 1]
						assert child_sum == self._index[pos]
		except:
			traceback.print_exc(file=sys.stdout)
			print('len', self._len)
			print('load', self._load)
			print('offset', self._offset)
			print('len_index', len(self._index))
			print('index', self._index)
			print('len_maxes', len(self._maxes))
			print('maxes', self._maxes)
			print('len_keys', len(self._keys))
			print('keys', self._keys)
			print('len_lists', len(self._lists))
			print('lists', self._lists)
			raise
SortedListWithKey = SortedKeyList
from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def A(n):
	return [0] * n

def AI(n, x):
	return [x] * n

def G(n):
	return [[] for i in range(n)]

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa = ifa[::-1]

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] < self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return (flag, prime)

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

@bootstrap
def gdfs(r, p):
	if len(g[r]) == 1 and p != -1:
		yield None
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None
t = N()
for i in range(t):
	n = N()
	q = RLL()
	vis = A(n + 1)
	mi = A(n)
	ma = A(n)
	mi[0] = ma[0] = q[0]
	vis[q[0]] = 1
	for i in range(1, n):
		if q[i] > q[i - 1]:
			vis[q[i]] = 1
			mi[i] = ma[i] = q[i]
	res = []
	for i in range(1, n + 1):
		if not vis[i]:
			res.append(i)
	s1 = sorted(res)
	s2 = SortedList(res)
	j = 0
	last = 0
	for i in range(n):
		if mi[i] == 0:
			mi[i] = s1[j]
			ind = s2.bisect(last)
			ma[i] = s2[ind - 1]
			s2.remove(ma[i])
			j += 1
		else:
			last = mi[i]
	print(*mi)
	print(*ma)


from sys import stdin, stdout
input = stdin.readline

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	p1 = [-1 for i in range(n)]
	p2 = [-1 for i in range(n)]
	last = -1
	for i in range(n):
		if a[i] != last:
			last = a[i]
			p1[i] = a[i]
			p2[i] = a[i]
	x = set(a)
	vals = []
	for i in range(1, n + 1):
		if i not in x:
			vals.append(i)
	c = 0
	for i in range(n):
		if p1[i] == -1:
			p1[i] = vals[c]
			c += 1
	vals = SortedList(vals)
	x = sorted(x)
	print(*p1)
	c = 0
	x.append(float('inf'))
	for i in range(1, n):
		if p2[i] != -1:
			c += 1
			continue
		ind = vals.bisect_left(x[c]) - 1
		p2[i] = vals[ind]
		vals.remove(vals[ind])
	print(*p2)


import bisect
import collections
import functools
import itertools
import math
import heapq
import random
import string

def repeat(_func=None, *, times=1):

	def decorator(func):

		@functools.wraps(func)
		def wrapper(*args, **kwargs):
			for _ in range(times):
				func(*args, **kwargs)
		return wrapper
	if _func is None:
		return decorator
	else:
		return decorator(_func)

def unpack(func=int):
	return map(func, input().split())

def l_unpack(func=int):
	return list(map(func, input().split()))

def getint():
	return int(input())

def getmatrix(rows):
	return [list(map(int, input().split())) for _ in range(rows)]

def display_matrix(mat):
	for i in range(len(mat)):
		print(mat[i])

def util(arr, n, last):
	output = [-1] * n
	vstd = [False] * (n + 1)
	vstd[arr[0]] = True
	output[0] = arr[0]
	deq = collections.deque([x for x in range(1, arr[0])])
	maxi = arr[0] - 1
	for i in range(1, n):
		if arr[i] > arr[i - 1]:
			output[i] = arr[i]
			vstd[arr[i]] = True
			while maxi + 1 < arr[i]:
				maxi += 1
				if not vstd[maxi]:
					deq.append(maxi)
		else:
			output[i] = deq.pop() if last else deq.popleft()
			vstd[output[i]] = True
	return output

@repeat(times=int(input()))
def main():
	n = getint()
	arr = l_unpack()
	lmin = util(arr, n, False)
	print(*lmin)
	lmax = util(arr, n, True)
	print(*lmax)
MOD = 10 ** 9 + 7
main()


from queue import Queue

def task1():
	p = []
	buffer = Queue()
	p.append(q[0])
	for x in range(1, q[0]):
		buffer.put(x)
	for i in range(n - 1):
		if q[i + 1] == q[i]:
			temp = buffer.get()
			p.append(temp)
		else:
			p.append(q[i + 1])
			for x in range(q[i] + 1, q[i + 1]):
				buffer.put(x)
	for val in p:
		print(val, end=' ')
	print()

def task2():
	p = []
	buffer = []
	p.append(q[0])
	for x in range(1, q[0]):
		buffer.append(x)
	for i in range(n - 1):
		if q[i + 1] == q[i]:
			temp = buffer.pop()
			p.append(temp)
		else:
			p.append(q[i + 1])
			for x in range(q[i] + 1, q[i + 1]):
				buffer.append(x)
	for val in p:
		print(val, end=' ')
	print()
t = int(input())
for _ in range(t):
	n = int(input())
	q = list(map(int, input().strip().split()))
	task1()
	task2()


from collections import deque

def odwroc(n, l):
	ustalone = [l[0]]
	maks = l[0]
	for i in range(1, n):
		if l[i] == maks:
			ustalone.append('x')
		else:
			ustalone.append(l[i])
			maks = l[i]
	return ustalone

def maxmin(n, p):
	(mi, ma) = (p.copy(), p.copy())
	(maxx, minn) = (deque(), deque())
	maks = 0
	for i in range(n):
		ob = ma[i]
		if ob == 'x':
			ma[i] = maxx.pop()
			mi[i] = minn.popleft()
		else:
			maxx.extend(range(maks + 1, ma[i]))
			minn.extend(range(maks + 1, ma[i]))
			maks = ma[i]
	print(' '.join(list(map(str, mi))))
	print(' '.join(list(map(str, ma))))
	return

def main():
	t = input()
	for i in range(int(t)):
		n = int(input())
		maxmin(n, odwroc(n, list(map(int, input().split()))))
	return
main()


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	p = [0] * (n + 1)
	q = [a[0]]
	p[a[0]] = 1
	k = 1
	for j in range(1, n):
		if a[j] == a[j - 1]:
			while p[k] == 1:
				k = k + 1
			q.append(k)
			p[k] = 1
		else:
			q.append(a[j])
			p[a[j]] = 1
	r = [a[0]]
	p = [j + 1 for j in range(a[0] - 1)]
	m = a[0]
	for j in range(1, n):
		if a[j] == a[j - 1]:
			r.append(p[-1])
			del p[-1]
		else:
			r.append(a[j])
			for k in range(m + 1, a[j]):
				p.append(k)
			m = a[j]
	print(' '.join(map(str, q)))
	print(' '.join(map(str, r)))


from sys import stdin, stdout
stdin.readline

def mp():
	return list(map(int, stdin.readline().strip().split()))

def it():
	return int(stdin.readline().strip())
from collections import defaultdict as dd, Counter as C, deque
from math import ceil, gcd, sqrt, factorial
for _ in range(it()):
	n = it()
	l = mp()
	mi = [l[0]]
	x = deque()
	for i in range(1, l[0]):
		x.append(i)
	for i in range(1, n):
		if l[i] != l[i - 1]:
			mi.append(l[i])
			for i in range(l[i - 1] + 1, l[i]):
				x.append(i)
		else:
			mi.append(x.popleft())
	print(*mi)
	ma = [l[0]]
	x = []
	for i in range(1, l[0]):
		x.append(i)
	for i in range(1, n):
		if l[i] != l[i - 1]:
			ma.append(l[i])
			for i in range(l[i - 1] + 1, l[i]):
				x.append(i)
		else:
			ma.append(x.pop())
	print(*ma)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	q = list(map(int, input().split()))
	p_min = [q[0]]
	s = set()
	s.add(q[0])
	curr = 1
	for i in range(1, n):
		if q[i] == q[i - 1]:
			while curr in s:
				curr += 1
			p_min.append(curr)
			s.add(curr)
			curr += 1
		else:
			p_min.append(q[i])
			s.add(q[i])
	p_max = [q[0]]
	s = set()
	s.add(q[0])
	prev = [i - 1 for i in range(n + 1)]
	for i in range(1, n):
		if q[i] == q[i - 1]:
			curr = prev[q[i]]
			while curr in s:
				curr = prev[curr]
			p_max.append(curr)
			s.add(curr)
			prev[q[i]] = curr
		else:
			p_max.append(q[i])
			s.add(q[i])
	print(*p_min)
	print(*p_max)


import sys
from sys import stdin
import heapq
tt = int(stdin.readline())
for loop in range(tt):
	n = int(stdin.readline())
	q = list(map(int, stdin.readline().split()))
	use = [False] * (n + 1)
	a = [None] * n
	for i in range(n):
		if i == 0 or q[i] != q[i - 1]:
			a[i] = q[i]
			use[a[i]] = True
	ind = 1
	for i in range(n):
		if a[i] == None:
			while use[ind]:
				ind += 1
			a[i] = ind
			ind += 1
	print(*a)
	b = [None] * n
	nex = 1
	que = []
	for i in range(n):
		if i == 0 or q[i] != q[i - 1]:
			b[i] = q[i]
			while nex < b[i]:
				heapq.heappush(que, -1 * nex)
				nex += 1
			nex += 1
		else:
			b[i] = -1 * heapq.heappop(que)
	print(*b)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	q = list(map(int, input().split()))
	x = [0] * n
	u = []
	p = 0
	for i in range(n):
		v = q[i]
		if v != p:
			x[i] = v
			u += [v]
			p = v
	y = x[:]
	e = []
	p = 0
	u = u[::-1]
	l = 1
	for i in range(n):
		if x[i] < 1:
			while l and l == u[-1]:
				l += 1
				u.pop()
			x[i] = l
			l += 1
			y[i] = e.pop()
		else:
			e += list(range(p + 1, x[i]))
			p = x[i]
	print(' '.join(map(str, x)))
	print(' '.join(map(str, y)))


import sys
import math
from itertools import permutations
from bisect import bisect_left
import heapq
from collections import deque

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()

def FACT(n, mod):
	s = 1
	facts = [1]
	for i in range(1, n + 1):
		s *= i
		s %= mod
		facts.append(s)
	return facts[n]

def C(n, k, mod):
	return FACT(n, mod) * pow(FACT(k, mod) * FACT(n - k, mod) % mod, mod - 2, mod) % mod

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)
for _ in range(II()):
	n = II()
	a = LI()
	b = [0 for i in range(n)]
	d = {}
	b[0] = a[0]
	d[b[0]] = 1
	for i in range(1, n):
		if a[i] != a[i - 1]:
			b[i] = a[i]
			d[b[i]] = 1
	temp = []
	for i in range(1, n + 1):
		if not d.get(i):
			temp.append(i)
	temp2 = temp[:]
	temp2.reverse()
	c = b[:]
	temp = [i for i in range(1, b[0])]
	m = b[0]
	for i in range(n):
		if b[i] == 0:
			b[i] = temp2.pop()
			c[i] = temp.pop()
			d[c[i]] = 1
		elif b[i] > m:
			for j in range(m + 1, b[i]):
				if not d.get(j):
					temp.append(j)
			m = b[i]
	print(*b)
	print(*c)


import sys
import math
import bisect
import heapq
from bisect import bisect_right
from sys import stdin, stdout

def get_ints_in_variables():
	return map(int, sys.stdin.readline().strip().split())

def get_int():
	return int(sys.stdin.readline())

def get_ints_in_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

def get_string():
	return sys.stdin.readline().strip()

def Solution(arr, n):
	a = arr
	mini = [a[0]]
	maxi = [a[0]]
	s = set(a)
	vis = [i for i in range(1, n + 1) if i not in s]
	vis2 = vis[:]
	i = 0
	j = len(vis) - 1
	for k in range(1, n):
		if a[k] == a[k - 1]:
			mini.append(vis[i])
			i += 1
			pos = bisect.bisect_left(vis2, a[k])
			if pos == 0:
				maxi.append(vis2[pos + 1])
				vis2.pop(pos + 1)
			else:
				maxi.append(vis2[pos - 1])
				vis2.pop(pos - 1)
		else:
			mini.append(a[k])
			maxi.append(a[k])
	print(*mini)
	print(*maxi)

def main():
	for _ in range(get_int()):
		n = get_int()
		arr = get_ints_in_list()
		Solution(arr, n)
main()


def updateQuery(BIT, index, val):
	while index < len(BIT):
		BIT[index] += val
		index += index & -index

def sumQuery(BIT, index):
	total = 0
	while index > 0:
		total += BIT[index]
		index -= index & -index
	return total

def rangeQuery(BIT, l, r):
	return sumQuery(BIT, r) - sumQuery(BIT, l - 1)

def findSmallest(BIT, x):
	low = 1
	high = x - 1
	smallest = -1
	while low <= high:
		mid = (low + high) // 2
		total = rangeQuery(BIT, 1, mid)
		if total == mid:
			smallest = mid + 1
			low = mid + 1
		else:
			high = mid - 1
	if smallest == -1:
		return 1
	return smallest

def findLargest(BIT, x):
	low = 1
	high = x
	largest = -1
	while low <= high:
		mid = (low + high) // 2
		total = rangeQuery(BIT, mid, x)
		if total == x - mid + 1:
			largest = mid - 1
			high = mid - 1
		else:
			low = mid + 1
	return largest

def solve(arr, n, ans):
	BIT_small = [0] * (n + 1)
	BIT_large = [0] * (n + 1)
	minimal = []
	maximal = []
	curr_max = 0
	for i in arr:
		if i > curr_max:
			minimal.append(str(i))
			maximal.append(str(i))
			updateQuery(BIT_small, i, 1)
			updateQuery(BIT_large, i, 1)
			curr_max = i
		else:
			smallest = findSmallest(BIT_small, i)
			largest = findLargest(BIT_large, i)
			minimal.append(str(smallest))
			maximal.append(str(largest))
			updateQuery(BIT_small, smallest, 1)
			updateQuery(BIT_large, largest, 1)
	ans.append(' '.join(minimal))
	ans.append(' '.join(maximal))

def main():
	t = int(input())
	ans = []
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		solve(arr, n, ans)
	print('\n'.join(ans))
main()


T = int(input())
minn = 1
ans1 = []
ans2 = []
for _ in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	d = {}
	val = [0] * (n + 1)
	p = 1
	min_per = []
	for i in arr:
		d[i] = d.get(i, 0) + 1
	for i in d:
		freq = d[i]
		min_per.append(i)
		val[i] = 1
		j = 0
		while j != freq - 1:
			if val[p] == 0:
				min_per.append(p)
				val[p] = 1
				p += 1
				j += 1
			else:
				p += 1
	max_per = []
	rem = []
	prev = 0
	for i in d:
		freq = d[i]
		max_per.append(i)
		for j in range(prev + 1, i):
			rem.append(j)
		prev = i
		for _ in range(freq - 1):
			max_per.append(rem.pop())
	print(*min_per)
	print(*max_per)


import sys
import math
import heapq
import bisect
from collections import Counter
from collections import defaultdict
from io import BytesIO, IOBase
import string

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None
		self.BUFSIZE = 8192

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_int():
	return int(input())

def get_ints():
	return list(map(int, input().split(' ')))

def get_int_grid(n):
	return [get_ints() for _ in range(n)]

def get_str():
	return input().strip()

def get_strs():
	return get_str().split(' ')

def flat_list(arr):
	return [item for subarr in arr for item in subarr]

def yes_no(b):
	if b:
		return 'YES'
	else:
		return 'NO'

def binary_search(good, left, right, delta=1, right_true=False):
	limits = [left, right]
	while limits[1] - limits[0] > delta:
		if delta == 1:
			mid = sum(limits) // 2
		else:
			mid = sum(limits) / 2
		if good(mid):
			limits[int(right_true)] = mid
		else:
			limits[int(~right_true)] = mid
	if good(limits[int(right_true)]):
		return limits[int(right_true)]
	else:
		return False

def prefix_sums(a):
	p = [0]
	for x in a:
		p.append(p[-1] + x)
	return p

def solve_a():
	(n, m, x) = get_ints()
	(row, col) = ((x - 1) % n, (x - 1) // n)
	return row * m + col + 1

def solve_b():
	(n, k) = get_ints()
	s = list(get_str())
	stars = [idx for idx in range(n) if s[idx] == '*']
	m = len(stars)
	idx = 0
	while idx < m:
		s[stars[idx]] = 'x'
		jdx = idx + 1
		while jdx < m - 1 and stars[jdx + 1] - stars[idx] <= k:
			jdx += 1
		idx = jdx
	return s.count('x')

def solve_c():
	a = get_str()
	b = get_str()
	n = len(a)
	m = len(b)
	tmp = 0
	for i in range(n):
		for j in range(i, n):
			if a[i:j + 1] in b:
				tmp = max(tmp, j - i + 1)
	return m + n - 2 * tmp

def solve_d():
	n = get_int()
	arr = get_ints()
	c = [-x for x in Counter(arr).values()]
	heapq.heapify(c)
	while len(c) > 1:
		x = -heapq.heappop(c) - 1
		y = -heapq.heappop(c) - 1
		if x:
			heapq.heappush(c, -x)
		if y:
			heapq.heappush(c, -y)
	return -sum(c)

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def solve_e():
	n = get_int()
	q = get_ints()
	p = [i for i in range(1, n + 1)]
	S1 = SortedList(p)
	S2 = SortedList(p)
	curr = 0
	r1 = []
	r2 = []
	for i in range(n):
		if q[i] == curr:
			r1.append(S1.pop(0))
			j = S2.bisect_left(q[i])
			r2.append(S2.pop(j - 1))
		else:
			r1.append(q[i])
			S1.remove(q[i])
			r2.append(q[i])
			S2.remove(q[i])
		curr = q[i]
	return (r1, r2)
t = get_int()
for _ in range(t):
	for ans in solve_e():
		print(*ans)


n = int(input())
from collections import deque
for i in range(n):
	a = int(input())
	b = list(map(int, input().split()))
	min_comb = [b[0]]
	max_comb = [b[0]]
	min_dec = deque([i for i in range(1, b[0])])
	max_dec = deque([i for i in range(1, b[0])])
	for i in range(1, len(b)):
		if b[i - 1] == b[i]:
			min_comb.append(min_dec.popleft())
			max_comb.append(max_dec.pop())
		if b[i - 1] != b[i]:
			min_comb.append(b[i])
			max_comb.append(b[i])
			for i in range(b[i - 1] + 1, b[i]):
				min_dec.append(i)
				max_dec.append(i)
	print(*min_comb)
	print(*max_comb)


from queue import deque
t = int(input())
for _ in range(t):
	n = int(input())
	q = list(map(int, input().split()))
	mi = 0
	l = [None] * n
	v = [None] * n
	d = deque()
	for i in range(n):
		if i == 0:
			l[i] = q[i]
			for j in range(mi + 1, q[i]):
				d.append(j)
			mi = q[i]
			continue
		if q[i] != q[i - 1]:
			l[i] = q[i]
			for j in range(mi + 1, q[i]):
				d.append(j)
			mi = q[i]
		else:
			l[i] = d.popleft()
	mi = 0
	d = deque()
	for i in range(n):
		if i == 0:
			v[i] = q[i]
			for j in range(mi + 1, q[i]):
				d.append(j)
			mi = q[i]
			continue
		if q[i] != q[i - 1]:
			v[i] = q[i]
			for j in range(mi + 1, q[i]):
				d.append(j)
			mi = q[i]
		else:
			v[i] = d.pop()
	print(*l)
	print(*v)


t = int(input())
for i in range(t):
	abc = set()
	n = int(input())
	w = list(range(1, n + 1))
	mw = w[::-1]
	q = [int(j) for j in input().split()]
	res = []
	mres = []
	j = 0
	for k in q:
		if k not in abc:
			abc |= {k}
			res.append(k)
		else:
			while w[j] in abc:
				j += 1
			res.append(w[j])
			abc |= {w[j]}
	j = 0
	abc = set()
	qwe = 0
	stack = []
	for k in q:
		if k not in abc:
			abc |= {k}
			mres.append(k)
			for y in range(qwe + 1, k):
				stack.append(y)
			qwe = k
		else:
			zxc = stack.pop()
			while zxc in abc:
				pass
			mres.append(zxc)
			abc |= {zxc}
	print(' '.join([str(k) for k in res]))
	print(' '.join([str(k) for k in mres]))


import os
from io import BytesIO, IOBase
import sys
from collections import defaultdict, deque, Counter
from bisect import *
from math import sqrt, pi, ceil, log, inf, gcd, floor
from itertools import permutations
from copy import deepcopy
from heapq import *

class SortedList:

	def __init__(self, iterable=None, _load=200):
		if iterable is None:
			iterable = []
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def fact(n, mo):
	f = [1]
	for i in range(1, n + 1):
		f.append(f[-1] * i % mo)
	invf = [0] * (n + 1)
	invf = pow(f[-1], mo - 2, mo)
	for i in range(n - 1, -1, -1):
		invf[i] = (i + 1) * invf[i + 1] % mo
	return (f, invf)

def mod(a, m):
	if a > m:
		return a % m
	return a

def decimal_to_base_b_converter(z, b):
	a = []
	while z:
		a.append(str(z % b))
		z = z // b
	return ''.join(a)

def base_subtraction(n, b):
	length = len(n)
	x = int(''.join(sorted(n, reverse=1)), b)
	y = int(''.join(sorted(n)), b)
	return decimal_to_base_b_converter(x - y, b).zfill(length)

def lcm(arr):
	l_c_m = arr[0]
	for i in range(1, len(arr)):
		l_c_m = l_c_m * arr[i] // gcd(l_c_m, arr[i])
	return l_c_m

def seieve_prime_factorisation(n):
	(p, i) = ([1] * (n + 1), 2)
	while i * i <= n:
		if p[i] == 1:
			for j in range(i * i, n + 1, i):
				p[j] = i
		i += 1
	return p

def prime_factorisation_by_seive(p, x):
	c = Counter()
	while p[x] != 1:
		c[p[x]] += 1
		x = x // p[x]
	c[x] += 1
	return c

def main():
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		b = [0] * (n + 1)
		c = []
		j = 1
		d = set()
		for i in a:
			if not b[i]:
				c.append(i)
			else:
				while j in d:
					j += 1
				c.append(j)
			d.add(c[-1])
			b[i] += 1
		e = []
		d = SortedList()
		for i in range(1, n + 1):
			d.add(i)
		for i in range(1, n + 1):
			if b[i]:
				z = d.bisect_left(i)
				f = []
				for k in range(b[i]):
					e.append(d[z])
					f.append(e[-1])
					z -= 1
				for j in f:
					d.discard(j)
		print(*c)
		print(*e)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	prev_max = 0
	min_ans = []
	temp = []
	max_ans = []
	temp2 = []
	index = 0
	for i in arr:
		if i > prev_max:
			min_ans.append(i)
			max_ans.append(i)
			for j in range(prev_max + 1, i):
				temp.append(j)
				temp2.append(j)
			prev_max = i
		else:
			min_ans.append(temp[index])
			index += 1
			max_ans.append(temp2[-1])
			temp2.pop()
	print(*min_ans)
	print(*max_ans)


import heapq, bisect
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = [0] * n
	ans1 = [0] * n
	ans[0] = l[0]
	ans1[0] = l[0]
	e = []
	e1 = []
	for i in range(1, l[0]):
		heapq.heappush(e, i)
		heapq.heappush(e1, -i)
	heapq.heapify(e)
	heapq.heapify(e1)
	for i in range(1, n):
		if l[i] == l[i - 1]:
			ans[i] = heapq.heappop(e)
			ans1[i] = -heapq.heappop(e1)
		else:
			for j in range(l[i - 1] + 1, l[i]):
				heapq.heappush(e, j)
				heapq.heappush(e1, -j)
			ans[i] = l[i]
			ans1[i] = l[i]
	print(*ans)
	print(*ans1)


import heapq

class Node:

	def __init__(self, key):
		self.left = None
		self.right = None
		self.data = key
from math import *
from sys import *
from heapq import *
from collections import defaultdict
from itertools import permutations
import os, sys
from io import IOBase, BytesIO
M = 10 ** 9 + 7

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		q = list(map(int, input().split()))
		dup = list(set(q))
		dct = defaultdict(int)
		for x in dup:
			dct[x] = 1
		arr = set()
		for i in range(1, n + 1):
			if dct[i] == 0:
				arr.add(i)
		arr = list(arr)
		heapq.heapify(arr)
		prev = -1
		for x in q:
			if prev == -1:
				prev = x
				print(x, end=' ')
			elif x == prev:
				val = heapq.heappop(arr)
				print(val, end=' ')
			else:
				print(x, end=' ')
				prev = x
		prev = -1
		print()
		maxq = []
		heapq.heapify(maxq)
		for x in q:
			if prev == -1:
				prev = x
				print(x, end=' ')
				for jj in range(1, x):
					heapq.heappush(maxq, -jj)
			elif x == prev:
				value = heapq.heappop(maxq)
				print(-value, end=' ')
			else:
				for jj in range(prev + 1, x):
					heapq.heappush(maxq, -jj)
				print(x, end=' ')
				prev = x
		print()
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import heapq

def calc(q, sign=1):
	n = len(q)
	values = []
	used = set()
	res = []
	next = 1
	for i in range(n):
		while next < q[i]:
			heapq.heappush(values, next * sign)
			next += 1
		if i == 0 or q[i - 1] != q[i]:
			assert q[i] not in used
			x = q[i]
		else:
			while abs(values[0]) in used:
				heapq.heappop(values)
			x = abs(heapq.heappop(values))
		used.add(x)
		res.append(x)
	return res
t = int(input())
for _ in range(t):
	n = int(input())
	q = list(map(int, input().split()))
	print(*calc(q))
	print(*calc(q, sign=-1))


import sys
from heapq import *
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
MOD = 10 ** 9 + 7

def solve():
	n = int(input())
	Q = tuple(map(int, input().split()))
	min_que = []
	min_res = []
	p = 0
	for q in Q:
		if p < q:
			for num in range(p + 1, q):
				heappush(min_que, num)
			min_res.append(q)
			p = q
		else:
			a = heappop(min_que)
			min_res.append(a)
	print(*min_res)
	max_que = []
	max_res = []
	p = 0
	for q in Q:
		if p < q:
			for num in range(p + 1, q):
				heappush(max_que, -num)
			max_res.append(q)
			p = q
		else:
			a = heappop(max_que) * -1
			max_res.append(a)
	print(*max_res)
t = int(input())
for _ in range(t):
	solve()


import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	s = SortedList()
	vis = [0] * (n + 1)
	vis[a[0]] = 1
	for i in range(1, n):
		if a[i] != a[i - 1]:
			vis[a[i]] = 1
	mini = [a[0]]
	maxi = [a[0]]
	for i in range(1, a[0]):
		s.add(i)
	prev = a[0]
	for i in range(1, n):
		if a[i] == a[i - 1]:
			mini.append(s.pop(0))
		else:
			for j in range(prev + 1, a[i]):
				s.add(j)
			prev = a[i]
			mini.append(a[i])
	s = SortedList()
	for i in range(1, a[0]):
		s.add(i)
	prev = a[0]
	for i in range(1, n):
		if a[i] == a[i - 1]:
			maxi.append(s.pop(len(s) - 1))
		else:
			for j in range(prev + 1, a[i]):
				s.add(j)
			prev = a[i]
			maxi.append(a[i])
	print(*mini)
	print(*maxi)


def test(n, q):
	tabmin = [False] * n
	tabmax = [False] * n
	lmin = [str(q[0])]
	lmax = [str(q[0])]
	prevq = q[0]
	tabmin[prevq - 1] = True
	tabmax[prevq - 1] = True
	mini = 1
	maxi = q[0] - 1
	jump = {}
	for i in range(1, n):
		if q[i] == prevq:
			while tabmin[mini - 1]:
				mini += 1
			lmin.append(str(mini))
			tabmin[mini - 1] = True
			while tabmax[maxi - 1]:
				maxi = jump.get(maxi, maxi - 1)
			lmax.append(str(maxi))
			tabmax[maxi - 1] = True
			jump[q[i]] = maxi
		else:
			prevq = q[i]
			lmin.append(str(prevq))
			lmax.append(str(prevq))
			tabmin[prevq - 1] = True
			tabmax[prevq - 1] = True
			maxi = prevq - 1
	print(' '.join(lmin))
	print(' '.join(lmax))
for kT in range(int(input())):
	n = int(input())
	q = list(map(int, input().split()))
	test(n, q)


import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import heapq
T = int(input())
r = 1
while r <= T:
	n = int(input())
	arr = list(map(int, input().split()))
	minimum = [0] * n
	maximum = [0] * n
	minimum[0] = arr[0]
	maximum[0] = arr[0]
	for i in range(1, n):
		if arr[i] > arr[i - 1]:
			minimum[i] = arr[i]
			maximum[i] = arr[i]
	minimumoccu = [False] * (n + 1)
	maximumstack = []
	minimumoccu[arr[0]] = True
	count = 1
	for i in range(1, n):
		if minimum[i] > 0:
			minimumoccu[minimum[i]] = True
			continue
		while minimumoccu[count]:
			count += 1
		minimum[i] = count
		minimumoccu[count] = True
	lastchange = arr[0]
	maximumstack.append(1)
	maximumstack.append(arr[0] - 1)
	for i in range(1, n):
		if maximum[i] > 0:
			maximumstack.append(lastchange + 1)
			maximumstack.append(maximum[i] - 1)
			lastchange = maximum[i]
		else:
			while maximumstack[-2] > maximumstack[-1]:
				maximumstack.pop()
				maximumstack.pop()
			maximum[i] = maximumstack[-1]
			maximumstack[-1] -= 1
	ans1 = ' '.join(map(str, minimum))
	ans2 = ' '.join(map(str, maximum))
	os.sys.stdout.write(str(ans1) + '\n')
	os.sys.stdout.write(str(ans2) + '\n')
	r += 1


import sys
from math import *
import threading
from heapq import *
from itertools import count
from pprint import pprint
from collections import defaultdict
from heapq import heapify, heappop, heappush
sys.setrecursionlimit(300000)
mod = 10 ** 9 + 7
inf = 10 ** 15
decision = ['NO', 'YES']
yes = 'YES'
no = 'NO'
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def npr(n, r):
	return factorial(n) % mod // (factorial(n - r) % mod) if n >= r else 0

def ncr(n, r):
	return factorial(n) % mod // (factorial(r) % mod * (factorial(n - r) % mod)) if n >= r else 0

def lower_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] >= num:
			answer = middle
			end = middle - 1
		else:
			start = middle + 1
	return answer

def upper_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] <= num:
			answer = middle
			start = middle + 1
		else:
			end = middle - 1
	return answer

def abs(x):
	return x if x >= 0 else -x

def binary_search(li, val):
	ans = -1
	lb = 0
	ub = len(li) - 1
	while lb <= ub:
		mid = (lb + ub) // 2
		if li[mid] > val:
			ub = mid - 1
		elif val > li[mid]:
			lb = mid + 1
		else:
			ans = mid
			break
	return ans

def kadane(x):
	sum_so_far = 0
	current_sum = 0
	for i in x:
		current_sum += i
		if current_sum < 0:
			current_sum = 0
		else:
			sum_so_far = max(sum_so_far, current_sum)
	return sum_so_far

def pref(li):
	pref_sum = [0]
	for i in li:
		pref_sum.append(pref_sum[-1] + i)
	return pref_sum

def SieveOfEratosthenes(n):
	prime = [{1, i} for i in range(n + 1)]
	p = 2
	while p <= n:
		for i in range(p * 2, n + 1, p):
			prime[i].add(p)
		p += 1
	return prime

def primefactors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n //= 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n //= i
	if n > 2:
		factors.append(n)
	return factors

def prod(li):
	ans = 1
	for i in li:
		ans *= i
	return ans

def sumk(a, b):
	print('called for', a, b)
	ans = a * (a + 1) // 2
	ans -= b * (b + 1) // 2
	return ans

def sumi(n):
	ans = 0
	if len(n) > 1:
		for x in n:
			ans += int(x)
		return ans
	else:
		return int(n)
karmanya = int(input())
while karmanya != 0:
	karmanya -= 1
	n = int(input())
	a = list(map(int, input().split()))
	maxheap = []
	minheap = []
	(ans, ans1) = ([a[0]], [a[0]])
	for i in range(1, a[0]):
		heappush(minheap, i)
		heappush(maxheap, -i)
	heapify(maxheap)
	heapify(minheap)
	for i in range(1, n):
		if a[i] == a[i - 1]:
			ans.append(heappop(minheap))
			ans1.append(-heappop(maxheap))
		else:
			for j in range(a[i - 1] + 1, a[i]):
				heappush(minheap, j)
				heappush(maxheap, -j)
			ans.append(a[i])
			ans1.append(a[i])
	print(*ans)
	print(*ans1)


def cf_710E(n: int, numbers: list):
	const = [None] * n
	temp = set()
	for (index, num) in enumerate(numbers):
		if num not in temp:
			const[index] = num
			temp.add(num)
	remainig = sorted(set(range(1, n + 1)).difference(temp))
	if not len(remainig):
		print(*const)
		print(*const)
		return
	i = 0
	MIN = const.copy()
	for (index, val) in enumerate(MIN):
		if val is None:
			MIN[index] = remainig[i]
			i += 1
	MAX = const.copy()
	currMax = -1
	for (index, val) in enumerate(MAX):
		if val is not None:
			currMax = val
			continue
		x = lowerBound(remainig, currMax)
		MAX[index] = remainig.pop(x)
	print(*MIN)
	print(*MAX)

def lowerBound(arr: list, element: int):
	answer = -1
	low = 0
	high = len(arr) - 1
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] < element:
			answer = mid
			low = mid + 1
		else:
			high = mid - 1
	return answer
for _ in range(int(input())):
	n = int(input())
	cf_710E(n, list(map(int, input().split())))


Z = input
r = range
for _ in [0] * int(Z()):
	n = int(Z())
	q = [*map(int, Z().split())]
	x = [0] * n
	u = []
	p = 0
	for i in r(n):
		v = q[i]
		if v != p:
			x[i] = v
			u += [v]
			p = v
	y = x[:]
	e = []
	p = 0
	u = u[::-1]
	l = 1
	for i in r(n):
		if x[i] < 1:
			while l and l == u[-1]:
				l += 1
				u.pop()
			x[i] = l
			l += 1
			y[i] = e.pop()
		else:
			e += [*r(p + 1, x[i])]
			p = x[i]
	print(*x, '\n', *y)


from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	q = [int(x) for x in input().split()]
	ans1 = []
	ans2 = []
	stack = []
	queue = []
	v = 0
	last = 0
	for i in range(n):
		if i == 0 or q[i] != q[i - 1]:
			for j in range(last + 1, q[i]):
				stack.append(j)
				queue.append(j)
			last = q[i]
			ans1.append(q[i])
			ans2.append(q[i])
		else:
			ans1.append(queue[v])
			v += 1
			ans2.append(stack.pop())
	print(*ans1)
	print(*ans2)


from collections import deque
import sys
inf = float('inf')
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	s1 = deque()
	s2 = deque()
	ans1 = [0] * n
	ans2 = [0] * n
	s = 0
	i = 0
	while i < n:
		num = arr[i]
		if num == s:
			ans1[i] = s1.popleft()
			ans2[i] = s2.pop()
		else:
			ans1[i] = num
			ans2[i] = num
			a = s + 1
			while a < num:
				s1.append(a)
				s2.append(a)
				a += 1
			s = num
		i += 1
	print(*ans1)
	print(*ans2)


import math
from collections import Counter
import bisect

def tis():
	return map(int, input().split(' '))

def tl():
	return list(map(int, input().split(' ')))
for _ in range(int(input())):
	n = int(input())
	q = tl()
	mn = [0 for i in range(n)]
	mx = [0 for i in range(n)]
	mn[0] = q[0]
	mx[0] = q[0]
	array = [q[0]]
	for i in range(1, n):
		if q[i] != q[i - 1]:
			mn[i] = q[i]
			mx[i] = q[i]
			array.append(q[i])
	nUsed = [i for i in range(1, n + 1)]
	for k in array:
		nUsed[k - 1] = -1
	ptr = 0
	for i in range(n):
		if mn[i] == 0:
			while nUsed[ptr] == -1:
				ptr += 1
			mn[i] = nUsed[ptr]
			ptr += 1
	print(*mn)
	maxx = [0] * n
	maxx[0] = q[0]
	for i in range(1, n):
		if q[i] != q[i - 1]:
			maxx[i] = q[i]
	s = set(maxx)
	curr = n
	left = []
	prev = 0
	for i in range(n):
		if maxx[i] == 0:
			maxx[i] = left.pop()
		else:
			for j in range(prev + 1, maxx[i]):
				left.append(j)
			prev = maxx[i]
	print(*maxx)


from sys import stdin, stdout
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import *
from random import *
input = stdin.readline
prin = stdout.write
from random import sample
from collections import Counter, deque
from math import sqrt, ceil, log2, gcd
mod = 10 ** 9 + 7

def f(arr, i, j, d, dist):
	if i == j:
		return
	nn = max(arr[i:j])
	for tl in range(i, j):
		if arr[tl] == nn:
			dist[tl] = d
			f(arr, i, tl, d + 1, dist)
			f(arr, tl + 1, j, d + 1, dist)

def ps(n):
	cp = 0
	lk = 0
	arr = {}
	cc = 0
	ans = 1
	while n % 2 == 0:
		n = n // 2
		lk += 1
		cc = 1
	if lk % 2 == 1:
		ans *= 2
	for ps in range(3, ceil(sqrt(n)) + 1, 2):
		lk = 0
		cc = 0
		while n % ps == 0:
			n = n // ps
			cc = 1
			lk += 1
		if lk % 2 == 1:
			ans *= ps
	if n != 1:
		ans *= n
	return ans

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def factorials(n, r):
	slr = n
	dpr = r
	qlr = 1
	qs = 1
	mod = 10 ** 9 + 7
	for ip in range(n - r + 1, n + 1):
		qlr = qlr * ip % mod
	for ij in range(1, r + 1):
		qs = qs * ij % mod
	ans = qlr * modInverse(qs) % mod
	return ans

def modInverse(b):
	qr = 10 ** 9 + 7
	return pow(b, qr - 2, qr)
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def power(arr):
	listrep = arr
	subsets = []
	for i in range(2 ** len(listrep)):
		subset = []
		for k in range(len(listrep)):
			if i & 1 << k:
				subset.append(listrep[k])
		subsets.append(subset)
	return subsets

def pda(n):
	list = []
	for i in range(1, int(sqrt(n) + 1)):
		if n % i == 0:
			if n // i == i:
				list.append(i)
			else:
				list.append(n // i)
				list.append(i)
	return list

def dis(xa, ya, xb, yb):
	return sqrt((xa - xb) ** 2 + (ya - yb) ** 2)

def ii():
	return int(input())

def ilist():
	return [int(x) for x in input().strip().split()]

def islist():
	return list(map(str, input().split().rstrip()))

def outfast(arr: list) -> str:
	ss = ''
	for ip in arr:
		ss += str(ip) + ' '
	ss += '\n'
	return prin(ss)

def kk(n):
	kp = 0
	while n % 2 == 0:
		n = n // 2
		kp += 1
	if n == 1:
		return [True, kp]
	else:
		return [False, 0]

def google(test, ans):
	return 'Case #' + str(test) + ': ' + str(ans)
t = int(input())
for jj in range(t):
	n = ii()
	arr = ilist()
	mins = [0] * n
	maxs = [0] * n
	mins[0] = maxs[0] = arr[0]
	nu = 1
	temp = []
	mi = {arr[0]}
	ma = {arr[0]}
	for bp in range(1, arr[0]):
		temp.append(bp)
	prev = arr[0]
	for i in range(1, n):
		if arr[i] != arr[i - 1]:
			mins[i] = arr[i]
			mi.add(arr[i])
			nt = arr[i]
			maxs[i] = arr[i]
			for bp in range(prev + 1, arr[i]):
				temp.append(bp)
			prev = arr[i]
		else:
			while nu in mi:
				nu += 1
			mins[i] = nu
			mi.add(nu)
			maxs[i] = temp.pop()
	print(*mins)
	print(*maxs)


import sys
input = sys.stdin.buffer.readline
for _ in range(int(input())):
	n = int(input())
	q = list(map(int, input().split()))
	mn = [] * n
	mx = [] * n
	nxt = [i + 1 for i in range(n + 2)]
	prv = [i - 1 for i in range(n + 2)]
	for i in range(n):
		if i == 0 or q[i] != q[i - 1]:
			mn.append(q[i])
			nxt[prv[q[i]]] = nxt[q[i]]
			prv[nxt[q[i]]] = prv[q[i]]
		else:
			mn.append(nxt[0])
			nxt[0] = nxt[nxt[0]]
			prv[nxt[0]] = 0
	prev = [i - 1 for i in range(n + 2)]
	for i in range(n):
		if i == 0 or q[i] != q[i - 1]:
			mx.append(q[i])
			prev[q[i] + 1] = prev[q[i]]
		else:
			mx.append(prev[q[i] + 1])
			prev[q[i] + 1] = prev[prev[q[i] + 1]]
	print(*mn)
	print(*mx)


from sys import stdin, stdout
(input, print) = (stdin.readline, stdout.write)

def main():
	t = int(input())
	while t > 0:
		t -= 1
		n = int(input())
		q = [*map(int, input().split())]
		x = [0] * n
		u = []
		p = 0
		for i in range(n):
			v = q[i]
			if v != p:
				x[i] = v
				u += [v]
				p = v
		y = x[:]
		e = []
		p = 0
		u = u[::-1]
		l = 1
		for i in range(n):
			if x[i] < 1:
				while l and l == u[-1]:
					l += 1
					u.pop()
				x[i] = l
				l += 1
				y[i] = e.pop()
			else:
				e += [*range(p + 1, x[i])]
				p = x[i]
		print(' '.join(map(str, x)))
		print('\n')
		print(' '.join(map(str, y)))
		print('\n')
main()


from collections import deque
for _ in range(int(input())):
	n = int(input())
	q = list(map(int, input().split()))
	(pmn, pmx) = (deque(), [])
	(mn, mx) = ([], [])
	cur = 1
	i = 0
	while i < n:
		mn.append(q[i])
		mx.append(q[i])
		while cur < q[i]:
			pmn.append(cur)
			pmx.append(cur)
			cur += 1
		cur += 1
		j = i + 1
		while j < n and q[i] == q[j]:
			j += 1
		for _ in range(j - i - 1):
			mn.append(pmn.popleft())
			mx.append(pmx.pop())
		i = j
	print(*mn)
	print(*mx)


import sys
input = sys.stdin.readline

def update(v, w):
	while v <= LEN:
		BIT[v] += w
		v += v & -v

def getvalue(v):
	ANS = 0
	while v != 0:
		ANS += BIT[v]
		v -= v & -v
	return ANS

def bisect_on_BIT(x):
	if x <= 0:
		return 0
	ANS = 0
	h = 1 << LEN.bit_length() - 1
	while h > 0:
		if ANS + h <= LEN and BIT[ANS + h] < x:
			x -= BIT[ANS + h]
			ANS += h
		h //= 2
	return ANS + 1
t = int(input())
for tests in range(t):
	n = int(input())
	Q = list(map(int, input().split()))
	Q.append(1 << 30)
	ANSMIN = [-1] * n
	ANSMAX = [-1] * n
	USE = [0] * (n + 2)
	LEN = n + 2
	BIT = [0] * (LEN + 1)
	for i in range(n):
		if Q[i] != Q[i - 1]:
			ANSMIN[i] = Q[i]
			ANSMAX[i] = Q[i]
			USE[Q[i]] = 1
	ind = 0
	USE[0] = 1
	for i in range(n + 1):
		if USE[i] == 0:
			update(i, 1)
	for i in range(n):
		while USE[ind] == 1:
			ind += 1
		if ANSMIN[i] == -1:
			ANSMIN[i] = ind
			ind += 1
	print(*ANSMIN)
	MAX = -1
	for i in range(n):
		MAX = max(MAX, ANSMAX[i])
		if ANSMAX[i] == -1:
			x = getvalue(MAX)
			y = bisect_on_BIT(x)
			ANSMAX[i] = y
			update(y, -1)
	print(*ANSMAX)


from collections import defaultdict
t = int(input())
for i in range(t):
	n = int(input())
	q = list(map(int, input().split()))
	dict1 = defaultdict(int)
	dict2 = defaultdict(int)
	minimal = q[:]
	maximal = q[:]
	dict2[q[0]] = dict1[q[0]] = 1
	if n == 1:
		print(*minimal)
		print(*maximal)
		continue
	isChanged = False
	maxtillNow = q[0]
	j = 1
	m = q[0] - 1
	for k in range(1, n):
		if q[k] > maxtillNow:
			dict2[q[k]] = 1
			dict1[q[k]] = 1
			if q[k] != maxtillNow + 1:
				m = q[k] - 1
			maxtillNow = q[k]
			continue
		elif q[k] == maxtillNow:
			while dict1[j] != 0:
				j += 1
			minimal[k] = j
			dict1[j] = 1
			while dict2[m] != 0:
				m -= 1
			maximal[k] = m
			dict2[m] = 1
	print(*minimal)
	print(*maximal)


import sys
input = sys.stdin.readline
from collections import Counter
from heapq import heappush, heappop, heapify
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	minA = [0] * n
	maxA = [0] * n
	seen = [0] * n
	right = {}
	idx = [0] * n
	for i in range(n):
		if not i or A[i] != A[i - 1]:
			if i:
				right[A[i - 1]] = A[i]
				idx[i - 1] = A[i - 1]
			minA[i] = maxA[i] = A[i]
			seen[A[i] - 1] = 1
	j = 0
	for i in range(n):
		if not minA[i]:
			while seen[j]:
				j += 1
			minA[i] = j + 1
			j += 1
	j = A[0]
	hp = []
	for i in range(1, A[0]):
		heappush(hp, -i)
	for i in range(n):
		if not maxA[i]:
			maxA[i] = -heappop(hp)
		if idx[i]:
			if maxA[i] != n:
				for k in range(idx[i] + 1, right[idx[i]]):
					heappush(hp, -k)
	print(*minA)
	print(*maxA)


from collections import OrderedDict
from itertools import groupby
for _ in range(int(input())):
	n = int(input())
	qarr = list(map(int, input().split()))
	desc = [(k, len(list(g)) - 1) for (k, g) in groupby(qarr)]
	arr = []
	s = OrderedDict()
	for x in range(1, n + 1):
		s[x] = True
	for (k, ln) in desc:
		arr.append(k)
		del s[k]
		for _ in range(ln):
			p = s.popitem(False)
			arr.append(p[0])
	print(*arr)
	arr = []
	s = OrderedDict()
	perm = []
	for x in range(1, n + 1):
		s[x] = True
	for (k, ln) in desc:
		arr.append(k)
		del s[k]
		while s:
			p = s.popitem(False)[0]
			if p > k:
				s[p] = True
				s.move_to_end(p, False)
				break
			perm.append(p)
		for _ in range(ln):
			arr.append(perm.pop())
	print(*arr)


import sys
from collections import deque
input = sys.stdin.readline

class Problem:

	def __init__(self):
		pass

	def solve(self):
		ans = 0
		ans = 0
		n = int(input())
		A = list(map(int, input().split()))
		dqs = deque()
		dql = deque()
		a = 1
		while a < A[0]:
			dqs.append(a)
			dql.append(a)
			a += 1
		ans = [[A[0]], [A[0]]]
		for i in range(1, n):
			if A[i] == A[i - 1]:
				ans[0].append(dqs.popleft())
				ans[1].append(dql.pop())
			else:
				a = A[i - 1] + 1
				while a < A[i]:
					dqs.append(a)
					dql.append(a)
					a += 1
				ans[0].append(A[i])
				ans[1].append(A[i])
		ans[0] = list(map(str, ans[0]))
		ans[1] = list(map(str, ans[1]))
		print(' '.join(ans[0]))
		print(' '.join(ans[1]))

def main():
	p = Problem()
	t = int(input())
	while t:
		p.solve()
		t -= 1
main()


from sys import stdin
import heapq

class MaxHeap:

	def __init__(self):
		self.data = []

	def top(self):
		return -self.data[0]

	def push(self, val):
		heapq.heappush(self.data, -val)

	def pop(self):
		return -heapq.heappop(self.data)

def max_push(heap, cur, prev):
	for i in range(cur, prev, -1):
		heap.push(i)

def min_push(heap, cur, prev):
	for i in range(cur, prev, -1):
		heapq.heappush(heap, i)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ar = arr[:]
	cur = ar[0]
	prev = ar[0]
	maxheap = MaxHeap()
	mi = [ar[0]]
	ma = [ar[0]]
	arr = []
	min_push(arr, ar[0] - 1, 0)
	max_push(maxheap, ar[0] - 1, 0)
	for i in range(1, n):
		cur = ar[i]
		if prev != cur:
			min_push(arr, cur - 1, prev)
			max_push(maxheap, cur - 1, prev)
			mi.append(ar[i])
			ma.append(ar[i])
		else:
			mi.append(heapq.heappop(arr))
			ma.append(maxheap.pop())
		prev = ar[i]
	print(' '.join(map(str, mi)))
	print(' '.join(map(str, ma)))


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt, log2
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def testcase(t):
	for pp in range(t):
		solve(pp)

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def modInverse(b):
	g = gcd(b, mod)
	if g != 1:
		return -1
	else:
		return pow(b, mod - 2, mod)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 10 ** 9 + 7

def solve(case):
	n = int(inp())
	a = lis()
	for i in range(n):
		a[i] -= 1
	minarr = [0] * n
	minarr[0] = a[0]
	for i in range(1, n):
		if a[i] == a[i - 1]:
			continue
		minarr[i] = a[i]
	vis = [0] * n
	for i in range(n):
		if minarr[i]:
			vis[minarr[i]] = 1
	i = 0
	for j in range(n):
		if minarr[j] == 0:
			while vis[i] == 1:
				i += 1
			minarr[j] = i
			vis[i] = 1
	for i in range(n):
		minarr[i] += 1
	maxarr = [0] * n
	maxarr[0] = a[0]
	for i in range(1, n):
		if a[i] == a[i - 1]:
			continue
		maxarr[i] = a[i]
	prev = 0
	h = []
	for i in range(maxarr[0]):
		heappush(h, -i)
	for i in range(1, n):
		if maxarr[i] == 0:
			continue
		else:
			for j in range(prev + 1, i):
				maxarr[j] = -heappop(h)
			for j in range(maxarr[prev] + 1, maxarr[i]):
				heappush(h, -j)
			prev = i
	for j in range(prev + 1, n):
		maxarr[j] = -heappop(h)
	for i in range(n):
		maxarr[i] += 1
	print(' '.join((str(i) for i in minarr)))
	print(' '.join((str(i) for i in maxarr)))
testcase(int(inp()))


from collections import deque
for _ in range(int(input())):
	n = int(input())
	q = list(map(int, input().split()))
	(minn, maxx, a, p1, p2) = ([], [], 0, deque(), deque())
	for i in range(n):
		c = q[i]
		if c == a:
			(minn.append(p1.popleft()), maxx.append(p2.pop()))
		else:
			(minn.append(c), maxx.append(c))
			for j in range(a + 1, c):
				p1.append(j)
				p2.append(j)
			a = c
	print(*minn)
	print(*maxx)


import queue
import math
import sys
from collections import deque
t = int(input())
for _ in range(t):
	n = int(input())
	Q = list(map(int, input().split(' ')))
	L1 = [None for i in range(n)]
	L2 = [None for i in range(n)]
	q0 = Q[0]
	(L1[0], L2[0]) = (q0, q0)
	assign_from1 = deque(range(1, q0))
	assign_from2 = deque(range(1, q0))
	maxx = q0
	for j in range(1, n):
		qj = Q[j]
		if maxx < qj:
			(L1[j], L2[j]) = (qj, qj)
			for i in range(maxx + 1, qj):
				assign_from1.append(i)
				assign_from2.append(i)
			maxx = max(maxx, qj)
		else:
			L1[j] = assign_from1.popleft()
			L2[j] = assign_from2.pop()
	print(*L1)
	print(*L2)


import sys
input = sys.stdin.readline
import heapq
t = int(input())
for _ in range(t):
	n = int(input())
	q = list(map(int, input().split()))
	ans_min = [0] * n
	(Max, Min) = (0, 1)
	ok = []
	heapq.heapify(ok)
	for i in range(n):
		if q[i] > Max:
			ans_min[i] = q[i]
			Max = q[i]
			for i in range(Min, Max):
				heapq.heappush(ok, i)
			Min = Max + 1
		else:
			v = heapq.heappop(ok)
			ans_min[i] = v
	ans_max = [0] * n
	(Max, Min) = (0, 1)
	ok = []
	heapq.heapify(ok)
	for i in range(n):
		if q[i] > Max:
			ans_max[i] = q[i]
			Max = q[i]
			for i in range(Min, Max):
				heapq.heappush(ok, -i)
			Min = Max + 1
		else:
			v = heapq.heappop(ok)
			ans_max[i] = -v
	print(*ans_min)
	print(*ans_max)


from bisect import bisect_left
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = set(a)
	left = []
	for i in range(1, n + 1):
		if i not in s:
			left.append(i)
	small = [a[0]]
	j = 0
	for i in range(1, n):
		if a[i] == a[i - 1]:
			small.append(left[j])
			j += 1
		else:
			small.append(a[i])
	large = [a[0]]
	for i in range(1, n):
		if a[i] == a[i - 1]:
			j = bisect_left(left, a[i]) - 1
			large.append(left[j])
			left.pop(j)
		else:
			large.append(a[i])
	print(*small)
	print(*large)


import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7

def lcm(x, y):
	return x * y / gcd(x, y)

def fact(x, mod=mod):
	ans = 1
	for i in range(1, x + 1):
		ans = ans * i % mod
	return ans

def arr2D(n, m, default=0):
	return [[default for j in range(m)] for i in range(n)]

def arr3D(n, m, r, default=0):
	return [[[default for k in range(r)] for j in range(m)] for i in range(n)]

def sortDictV(x):
	return {k: v for (k, v) in sorted(x.items(), key=lambda item: item[1])}

class DSU:

	def __init__(self, length):
		self.length = length
		self.parent = [-1] * self.length

	def getParent(self, node, start):
		if node >= self.length:
			return False
		if self.parent[node] < 0:
			if start != node:
				self.parent[start] = node
			return node
		return self.getParent(self.parent[node], start)

	def union(self, node1, node2):
		parent1 = self.getParent(node1, node1)
		parent2 = self.getParent(node2, node2)
		if parent1 == parent2:
			return False
		elif self.parent[parent1] <= self.parent[parent2]:
			self.parent[parent1] += self.parent[parent2]
			self.parent[parent2] = parent1
		else:
			self.parent[parent2] += self.parent[parent1]
			self.parent[parent1] = parent2
		return True

	def getCount(self, node):
		return -self.parent[self.getParent(node, node)]

def exact(num):
	if abs(num - round(num)) <= 10 ** (-9):
		return round(num)
	return num

def minn(n, lst):
	vis = [0] * (n + 3)
	for i in lst:
		vis[i] = 1
	val = -1
	cur = [0] * (n + 2)
	lst1 = sorted(list(set(lst)))
	lst1 = [0] + lst1
	for i in range(len(lst1) - 1):
		if lst1[i] != lst1[i + 1] - 1:
			val = lst1[i] + 1
			break
	ans = []
	for i in lst:
		if cur[i] == 0:
			cur[i] = 1
			ans.append(i)
		else:
			ans.append(val)
			val += 1
			while vis[val] == 1:
				val += 1
	return ans

def maxx(n, lst):
	vis = [0] * (n + 3)
	for i in lst:
		vis[i] = 1
	nxt = {}
	for i in range(1, n + 1):
		nxt[i] = i - 1
	ans = []
	cur = [0] * (n + 2)
	for i in lst:
		if cur[i] == 0:
			cur[i] = 1
			ans.append(i)
		else:
			val = i - 1
			val1 = val
			while vis[val] == 1:
				val = nxt[val]
			nxt[val1] = val - 1
			ans.append(val)
			vis[val] = 1
	return ans

def p(lst):
	for i in lst:
		print(i, end=' ')
	print()

def solve(n, lst):
	p(minn(n, lst))
	p(maxx(n, lst))
for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	solve(n, lst)


import heapq
t = int(input())
for _ in range(t):
	_ = input()
	arr = [int(it) for it in input().split(' ')]
	max_perm_arr = []
	max_perm_arr.append(arr[0])
	min_perm_arr = []
	min_perm_arr.append(arr[0])
	max_q = []
	min_q = []
	for i in range(1, arr[0]):
		heapq.heappush(max_q, -i)
		heapq.heappush(min_q, i)
	vis_max = set([arr[0]])
	vis_min = set([arr[0]])
	for i in range(1, len(arr)):
		if arr[i] > arr[i - 1]:
			max_perm_arr.append(arr[i])
			vis_max.add(arr[i])
			min_perm_arr.append(arr[i])
			vis_min.add(arr[i])
			for j in range(arr[i - 1], arr[i]):
				if j in vis_max:
					pass
				else:
					heapq.heappush(max_q, -j)
				if j in vis_min:
					pass
				else:
					heapq.heappush(min_q, j)
		else:
			max_perm_arr.append(-heapq.heappop(max_q))
			vis_max.add(max_perm_arr[-1])
			min_perm_arr.append(heapq.heappop(min_q))
			vis_min.add(min_perm_arr[-1])
	print(*min_perm_arr)
	print(*max_perm_arr)


from heapq import heappush, heappop

def get_input():
	l = [int(e) for e in input().split()]
	return l

def main(q, n):
	min_p = []
	max_p = []
	heap_min = []
	heap_max = []
	v = 0
	for i in range(n):
		vnew = q[i]
		if vnew > v:
			for j in range(v + 1, vnew):
				heappush(heap_min, j)
				heappush(heap_max, -j)
			min_p.append(vnew)
			max_p.append(vnew)
		else:
			min_p.append(heappop(heap_min))
			max_p.append(-heappop(heap_max))
		v = vnew
	print(*min_p)
	print(*max_p)
t = get_input()[0]
for _ in range(t):
	n = get_input()[0]
	q = get_input()
	main(q, n)


for ad in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	key = l[0]
	x = [key]
	z = [i for i in range(1, key)]
	for i in range(1, n):
		if key != l[i]:
			z += [i for i in range(key + 1, l[i])]
			key = l[i]
			x.append(key)
		else:
			x.append(z.pop())
	a = list(set(l))
	a.sort()
	j = 0
	b = []
	for i in range(1, n + 1):
		if i == a[j]:
			j += 1
		else:
			b.append(i)
	key = l[0]
	j = 0
	for i in range(1, n):
		if l[i] == key:
			l[i] = b[j]
			j += 1
		else:
			key = l[i]
	print(*l)
	print(*x)


import sys
mod = 1000000007
input = lambda : sys.stdin.readline().rstrip('\r\n')
from _collections import deque
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = set()
	b = [a[0]]
	s.add(a[0])
	ck = 1
	for i in range(1, n):
		if a[i] == a[i - 1]:
			while ck in s and ck < n:
				ck += 1
			if ck not in s:
				b.append(ck)
				s.add(ck)
				ck += 1
		else:
			b.append(a[i])
			s.add(a[i])
	print(*b)
	s = set()
	c = [a[0]]
	ck = 1
	d = deque()
	while ck != a[0]:
		d.append(ck)
		ck += 1
	ck += 1
	for i in range(1, n):
		if a[i] == a[i - 1]:
			c.append(d.pop())
		else:
			while ck != a[i]:
				d.append(ck)
				ck += 1
			c.append(a[i])
			ck += 1
	print(*c)


def main():
	tt = int(input())
	while tt > 0:
		tt -= 1
		n = int(input())
		a = [int(u) for u in input().split()]
		ans1 = [0 for i in range(n)]
		prev = 0
		not_used = []
		for i in range(n):
			if a[i] != prev:
				ans1[i] = a[i]
				for j in range(prev + 1, a[i]):
					not_used.append(j)
				prev = a[i]
		not_used.reverse()
		for i in range(n):
			if ans1[i] == 0:
				ans1[i] = not_used.pop()
		for i in range(n):
			print(ans1[i], end=' ')
		print()
		not_used = []
		ans2 = [0 for i in range(n)]
		prev = 0
		for i in range(n):
			if a[i] != prev:
				ans2[i] = a[i]
				for j in range(prev + 1, a[i]):
					not_used.append(j)
				prev = a[i]
			else:
				ans2[i] = not_used.pop()
		for i in range(n):
			print(ans2[i], end=' ')
		print()
main()


import math
from collections import deque
t = int(input())

def get_answer(n, q):
	s1 = deque()
	s2 = deque()
	ans1 = [0] * n
	ans2 = [0] * n
	s = 0
	i = 0
	while i < n:
		num = q[i]
		if num == s:
			ans1[i] = s1.popleft()
			ans2[i] = s2.pop()
		else:
			ans1[i] = num
			ans2[i] = num
			a = s + 1
			while a < num:
				s1.append(a)
				s2.append(a)
				a += 1
			s = num
		i += 1
	print(*ans1)
	print(*ans2)
for _ in range(t):
	n = int(input())
	q = list(map(int, input().split()))
	get_answer(n, q)


def count():
	for i in a:
		c[i] += 1

def l_min():
	(ml, q) = ([a[0]], [])
	ind = 0
	for i in range(1, n):
		if not c[i]:
			q.append(i)
		if a[i - 1] != a[i]:
			for j in range(i - 1, i - c[a[i - 1]], -1):
				ml.append(q[ind])
				ind += 1
			ml.append(a[i])
	for i in range(n - 1, n - c[a[-1]], -1):
		ml.append(q[ind])
		ind += 1
	return ml

def l_max():
	(mal, s) = ([a[0]], [])
	prev = 0
	for i in range(1, n):
		if a[i - 1] != a[i]:
			for j in range(i - 1, i - c[a[i - 1]], -1):
				mal.append(s[-1])
				s.pop()
			mal.append(a[i])
		if prev != a[i - 1]:
			for j in range(prev + 1, a[i - 1]):
				s.append(j)
			prev = a[i - 1]
	if prev != a[-1]:
		for j in range(prev + 1, a[-1]):
			s.append(j)
	for i in range(n - 1, n - c[a[-1]], -1):
		mal.append(s[-1])
		s.pop()
	return mal
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = [0] * (n + 1)
	count()
	print(*l_min())
	print(*l_max())


import heapq
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = set()
	e = []
	for i in l:
		if i in s:
			continue
		s.add(i)
	for i in range(1, n + 1):
		if i in s:
			continue
		e.append(i)
	a = e[::-1]
	am = [0] * n
	for i in range(n):
		x = l[i]
		if x in s:
			am[i] = x
			s.remove(x)
		else:
			am[i] = a.pop()
	h = []
	ama = [0] * n
	heapq.heapify(h)
	i = 0
	prev = 0
	while i < n:
		j = i
		while j < n:
			if l[j] == l[i]:
				pass
			else:
				break
			j = j + 1
		w = j
		ama[i] = am[i]
		k = i + 1
		cnt = l[i] - 1
		er = prev
		prev = am[i]
		while cnt > er:
			heapq.heappush(h, -1 * cnt)
			cnt -= 1
		while k < w:
			cnt = -1 * heapq.heappop(h)
			ama[k] = cnt
			k += 1
		i = w
	print(*am)
	print(*ama)


from collections import defaultdict
r = lambda : list(map(int, input().split()))
t = int(input())
for _ in range(t):
	n = int(input())
	arr = r()
	a = []
	b = []
	x = 0
	small = 1
	used = defaultdict(lambda : 0)
	for i in arr:
		if i != x:
			used[i] = 1
			a.append(i)
			x = i
		else:
			while used[small]:
				small += 1
			used[small] = 1
			a.append(small)
	print(*a)
	a = []
	x = 0
	small = 0
	prev = 0
	used = defaultdict(lambda : 0)
	for i in arr:
		if i != x:
			used[i] = 1
			a.append(i)
			x = i
			if x - 1 > small and (not used[x - 1]):
				small = i - 1
		else:
			while small and used[small]:
				small -= 1
			used[small] = 1
			a.append(small)
	print(*a)


import os
import sys
from io import BytesIO, IOBase

class FastIO(IOBase):
	newlines = 0
	BUFSIZE = 8192

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self.BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self.BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def read_int_list():
	return list(map(int, input().split()))

def read_int_tuple():
	return tuple(map(int, input().split()))

def read_int():
	return int(input())
import bisect

def lower_bound(num_list, target_num):
	return bisect.bisect_left(num_list, target_num, lo=0, hi=len(num_list))
t = read_int()
for _ in range(t):
	n = read_int()
	q = read_int_list()
	(pivot, i, j) = (1, 0, 0)
	(rest_min, rest_max) = ([], [])
	(ans_min, ans_max) = ([], [])
	while i < n:
		rest_min.extend(list(range(pivot, q[i])))
		rest_max.extend(list(range(pivot, q[i])))
		pivot = q[i] + 1
		x = q[i]
		ans_min.append(x)
		ans_max.append(x)
		i += 1
		if i >= n:
			break
		while q[i] == x:
			ans_min.append(rest_min[j])
			j += 1
			ans_max.append(rest_max.pop())
			i += 1
			if i == n:
				break
	print(*ans_min)
	print(*ans_max)


T = int(input())
for t in range(T):
	n = int(input())
	q = [int(ea) for ea in input().split(' ')]
	maxP = [0 for i in range(n)]
	minP = [0 for i in range(n)]
	prev = -1
	numsLeft = set(range(1, n + 1))
	lowerThanMe = {ea: ea - 1 for ea in range(1, n + 1)}
	higherThanMe = {ea: ea + 1 for ea in range(1, n + 1)}
	for i in range(n):
		if q[i] != prev:
			cur = q[i]
			maxP[i] = cur
			minP[i] = cur
			numsLeft.remove(cur)
		prev = q[i]
	numsLeftForMin = sorted(list(numsLeft))
	ni = 0
	for i in range(n):
		if minP[i] == 0:
			minP[i] = numsLeftForMin[ni]
			ni += 1
	for i in range(n):
		if maxP[i] == 0:
			cur = maxP[i - 1]
			while cur not in numsLeft:
				higherThanMe[lowerThanMe[cur]] = higherThanMe[cur]
				lowerThanMe[higherThanMe[cur]] = lowerThanMe[cur]
				cur = lowerThanMe[cur]
			maxP[i] = cur
			numsLeft.remove(cur)
	print(*minP)
	print(*maxP)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	vis = [0] * (n + 1)
	vis[a[0]] = 1
	for i in range(1, n):
		if a[i] != a[i - 1]:
			vis[a[i]] = 1
	mini = [a[0]]
	maxi = [a[0]]
	available = []
	for i in range(1, n + 1):
		if vis[i] == 0:
			available.append(i)
	available.reverse()
	for i in range(1, n):
		if a[i] == a[i - 1]:
			mini.append(available.pop())
		else:
			mini.append(a[i])
	available = []
	prev = 1
	for i in range(1, n):
		for j in range(prev, a[i] + 1):
			if vis[j] == 0:
				vis[j] = 1
				available.append(j)
			prev = j
		if a[i] == a[i - 1]:
			maxi.append(available.pop())
		else:
			maxi.append(a[i])
	print(*mini)
	print(*maxi)


class SegmentTree:

	def __init__(self, array, f=lambda x, y: x + y, inf=0):
		self.f = f
		self.id = inf
		if isinstance(array, int):
			self.n = array
			self.tree = [self.id] * (self.n << 1)
		else:
			self.n = len(array)
			self.tree = [self.id] * (self.n << 1)
			for i in range(len(array)):
				self.tree[self.n + i] = array[i]
			for i in range(self.n - 1, 0, -1):
				self.tree[i] = self.f(self.tree[i << 1], self.tree[i << 1 | 1])

	def get(self, i):
		return self.tree[i + self.n]

	def update(self, i, x):
		i += self.n
		self.tree[i] = x
		while i > 1:
			i >>= 1
			self.tree[i] = self.f(self.tree[i << 1], self.tree[i << 1 | 1])

	def query(self, l, r):
		l += self.n
		r += self.n
		(lf, rf) = (self.id, self.id)
		while l < r:
			if l & 1:
				lf = self.f(lf, self.tree[l])
				l += 1
			if r & 1:
				r -= 1
				rf = self.f(self.tree[r], rf)
			l >>= 1
			r >>= 1
		return self.f(lf, rf)

	def query_all(self):
		return self.tree[1]

	def display(self):
		for i in range(self.n, self.n << 1):
			print(self.tree[i], end=' ')
			while i % 2 == 0:
				i >>= 1
				print(self.tree[i], end=' ')
			print()

	def min_left(self, l, r, f, sss):
		nr = r
		(lv, rv) = ([], [])
		l += self.n
		r += self.n
		while l < r:
			if l & 1:
				lv.append(l)
				l += 1
			if r & 1:
				r -= 1
				rv.append(r)
			l >>= 1
			r >>= 1
		now = self.id
		for i in lv + rv[::-1]:
			if f(now, self.tree[i], sss):
				while True:
					if f(now, self.tree[i], sss):
						if i >= self.n:
							return i - self.n + 1
						i <<= 1
					else:
						now = self.f(now, self.tree[i])
						i += 1
			else:
				now = self.f(now, self.tree[i])
		return nr + 1

	def max_right(self, l, r, f, sss):
		nl = l
		(lv, rv) = ([], [])
		l += self.n
		r += self.n
		while l < r:
			if l & 1:
				lv.append(l)
				l += 1
			if r & 1:
				r -= 1
				rv.append(r)
			l >>= 1
			r >>= 1
		now = self.id
		for i in rv + lv[::-1]:
			if f(self.tree[i], now, sss):
				while True:
					if f(self.tree[i], now, sss):
						if i >= self.n:
							return i - self.n + 1
						i <<= 1
						i += 1
					else:
						now = self.f(self.tree[i], now)
						i -= 1
			else:
				now = self.f(self.tree[i], now)
		return nl
import sys
input = sys.stdin.readline
t = int(input())
while t:
	t -= 1
	n = int(input())
	p = list(map(int, input().split()))
	ma = [p[0]]
	mi = [p[0]]
	a = [i for i in range(n + 1)]
	a[p[0]] = 1000000000.0
	a[0] = 1000000000.0
	S2 = SegmentTree(a, min, 1000000000.0)
	a[p[0]] = -1
	a[0] = -1
	S1 = SegmentTree(a, max, -1)
	for i in range(n - 1):
		if p[i] == p[i + 1]:
			r = S1.query(0, p[i + 1])
			s = S2.query(0, p[i + 1])
			ma.append(r)
			mi.append(s)
			S1.update(r, -1)
			S2.update(s, 1000000000.0)
		else:
			ma.append(p[i + 1])
			mi.append(p[i + 1])
			S1.update(p[i + 1], -1)
			S2.update(p[i + 1], 1000000000.0)
	print(*mi)
	print(*ma)


for _ in range(int(input())):
	n = int(input())
	q = list(map(int, input().split()))
	maxy = []
	miny = []
	M = []
	m = []
	count = 1
	i = 0
	j = 0
	while i < n:
		num = q[i]
		while num > count:
			maxy.append(count)
			miny.append(count)
			count = count + 1
		count = count + 1
		i = i + 1
		M.append(num)
		m.append(num)
		if i < n:
			while num == q[i]:
				m.append(miny[j])
				j += 1
				M.append(maxy[-1])
				maxy.pop()
				i += 1
				if i == n:
					break
	print(*m)
	print(*M)


from heapq import heapify, heappush, heappop
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	mnp = [0] * n
	mxp = [0] * n
	mnp[0] = arr[0]
	mxp[0] = arr[0]
	p = []
	per = []
	for i in range(1, arr[0]):
		heappush(p, i)
		heappush(per, -i)
	for i in range(1, n):
		if arr[i] != arr[i - 1]:
			for j in range(arr[i - 1] + 1, arr[i]):
				heappush(p, j)
				heappush(per, -j)
			mnp[i] = arr[i]
			mxp[i] = arr[i]
		else:
			mxp[i] = -1 * heappop(per)
			mnp[i] = heappop(p)
	print(*mnp)
	print(*mxp)


import sys
from collections import Counter
from heapq import heappop, heappush
input = sys.stdin.readline

def ri():
	return [int(i) for i in input().split()]

def main():
	t = ri()[0]
	for _ in range(t):
		n = ri()[0]
		q = ri()
		(hmx, hmi) = ([], [])
		pmx = 0
		resmx = []
		resmi = []
		for e in q:
			if e > pmx:
				for x in range(pmx + 1, e):
					heappush(hmx, -x)
					heappush(hmi, x)
				resmx.append(e)
				resmi.append(e)
				pmx = e
			else:
				resmx.append(-heappop(hmx))
				resmi.append(heappop(hmi))
		print(*resmi)
		print(*resmx)
main()


for _ in range(int(input())):
	n = int(input())
	q = list(map(int, input().split()))
	p = []
	p1 = []
	for i in range(1, n + 1):
		p.append(i)
		p1.append(i)
	mn = [0] * n
	mn[0] = q[0]
	p[q[0] - 1] = 0
	k = 0
	for i in range(1, n):
		if q[i] == q[i - 1]:
			mn[i] = p[k]
			p[k] = 0
			k += 1
			while k < n and p[k] == 0:
				k += 1
		else:
			mn[i] = q[i]
			p[q[i] - 1] = 0
			while k < n and p[k] == 0:
				k += 1
	print(*mn, sep=' ')
	mx = [0] * n
	mx[0] = q[0]
	curr = q[0]
	p2 = p1[:q[0] - 1]
	for i in range(1, n):
		if q[i] == q[i - 1]:
			mx[i] = p2[-1]
			p2.pop(-1)
		else:
			mx[i] = q[i]
			p2 += p1[curr:q[i] - 1]
			curr = q[i]
	print(*mx, sep=' ')


import sys
from collections import deque

def print_arr(arr):
	print(' '.join([str(n) for n in arr]))

def solve(nums):
	i = 0
	stack_max = []
	dq_min = deque()
	cur = 1
	mins = [0] * len(nums)
	maxs = [0] * len(nums)
	while i < len(nums):
		if i == 0 or nums[i] != nums[i - 1]:
			while cur < nums[i]:
				stack_max.append(cur)
				dq_min.append(cur)
				cur += 1
			cur += 1
			mins[i] = nums[i]
			maxs[i] = nums[i]
			i += 1
		else:
			while i < len(nums) and nums[i] == nums[i - 1]:
				mins[i] = dq_min.popleft()
				maxs[i] = stack_max.pop()
				i += 1
	return (mins, maxs)
t = int(sys.stdin.readline().strip())
for _ in range(t):
	line = sys.stdin.readline().strip()
	n = list(map(int, line.split()))[0]
	line = sys.stdin.readline().strip()
	nums = list(map(int, line.split()))
	(minimum, maximum) = solve(nums)
	print_arr(minimum)
	print_arr(maximum)


from collections import deque
t = int(input())
for i in range(t):
	n = int(input())
	q = input().split()
	q = list(map(int, q))
	q.insert(0, 0)
	nxt = deque()
	for i in range(1, n + 1):
		if q[i] > q[i - 1]:
			print(q[i], end=' ')
			nxt.extend([j for j in range(q[i - 1] + 1, q[i])])
		else:
			print(nxt[0], end=' ')
			nxt.popleft()
	print()
	for i in range(1, n + 1):
		if q[i] > q[i - 1]:
			print(q[i], end=' ')
			nxt.extend([j for j in range(q[i - 1] + 1, q[i])])
		else:
			print(nxt[-1], end=' ')
			nxt.pop()
	print()


import sys, io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
read = lambda : map(int, input().split())
O = []
for _ in range(int(input())):
	n = int(input())
	q = list(read())
	d1 = [0] * n
	u = []
	p = 0
	for i in range(n):
		if q[i] != p:
			d1[i] = q[i]
			u.append(q[i])
			p = q[i]
	d2 = d1[:]
	e = []
	p = 0
	u = u[::-1]
	l = 1
	for i in range(n):
		if d1[i] < 1:
			while l and l == u[-1]:
				l += 1
				u.pop()
			d1[i] = l
			l += 1
			d2[i] = e.pop()
		else:
			for j in range(p + 1, d1[i]):
				e.append(j)
			p = d1[i]
	O.append(' '.join(map(str, d1)))
	O.append(' '.join(map(str, d2)))
print('\n'.join(O))


from sys import stdin
input = stdin.readline

def per(l, arr):
	if arr[0] == arr[-1]:
		lex_min = [arr[0]] + [i for i in range(1, arr[0])]
		lex_max = [arr[0]] + [i for i in range(arr[0] - 1, 0, -1)]
	else:
		(lex_min, lex_max) = ([arr[0]] + [0] * (l - 1), [arr[0]] + [0] * (l - 1))
		(ls_min, ls_max) = ([i for i in range(1, arr[0])], [i for i in range(arr[0] - 1, 0, -1)])
		ind = 0
		for i in range(1, l):
			if arr[i - 1] == arr[i]:
				(lex_min[i], lex_max[i]) = (ls_min[ind], ls_max[ind])
				ind += 1
			else:
				(lex_min[i], lex_max[i]) = (arr[i], arr[i])
				x = len(lex_min)
				ls_min[x:x] = [i for i in range(arr[i - 1] + 1, arr[i])]
				ls_max[ind:ind] = [i for i in range(arr[i] - 1, arr[i - 1], -1)]
	print(*lex_min)
	print(*lex_max)
for test in range(int(input())):
	n = int(input())
	lst = list(map(int, input().strip().split()))
	per(n, lst)


def ints():
	return [int(x) for x in input().split(' ')]

def find_index(ranges, x, i, j):
	if i == j:
		return i
	if i == j - 1:
		return j if ranges[j][0] <= x else i
	m = (i + j) // 2
	(a, b) = ranges[m]
	if x < a:
		return find_index(ranges, x, i, m)
	if x > b:
		return find_index(ranges, x, m, j)
	return m

def remove_item(ranges, x):
	i = find_index(ranges, x, 0, len(ranges) - 1)
	(a, b) = ranges[i]
	if a == b:
		ranges.pop(i)
		return ranges
	if x == a:
		ranges[i][0] += 1
		return ranges
	if x == b:
		ranges[i][1] -= 1
		return ranges
	return ranges[0:i] + [[a, x - 1], [x + 1, b]] + ranges[i + 1:]
for _ in range(int(input())):
	n = int(input())
	q = ints()
	up = set([i + 1 for i in range(n)])
	down = [[1, n]]
	last = None
	for i in range(n):
		if q[i] == last:
			q[i] = 0
		else:
			up.remove(q[i])
			down = remove_item(down, q[i])
			last = q[i]
	up = list(up)
	up.sort()
	p = q[:]
	j = 0
	last = q[0]
	for i in range(n):
		if p[i] == 0:
			p[i] = up[j]
			j += 1
			k = find_index(down, last, 0, len(down) - 1)
			(a, b) = down[k]
			q[i] = b
			if a == b:
				down.pop(k)
			else:
				down[k][1] -= 1
		else:
			last = q[i]
	print(' '.join([str(x) for x in p]))
	print(' '.join([str(x) for x in q]))


from heapq import heappush, heappop
t = int(input())
for _ in range(t):
	n = int(input())
	q = list(map(int, input().split()))

	def calc(p):
		ans = []
		ma = 0
		h = []
		for i in range(n):
			if q[i] > ma:
				for j in range(ma + 1, q[i]):
					heappush(h, p * j)
				ans.append(q[i])
				ma = q[i]
			else:
				x = p * heappop(h)
				ans.append(x)
		return ans
	print(*calc(1))
	print(*calc(-1))


import heapq

def get_min_max(arr, n):
	min_val = [str(arr[0])]
	max_val = [str(arr[0])]
	current_max = arr[0]
	min_heap = [i for i in range(1, arr[0])]
	max_heap = [-i for i in range(1, arr[0])]
	heapq.heapify(min_heap)
	heapq.heapify(max_heap)
	for i in arr[1:]:
		if i > current_max:
			for j in range(current_max + 1, i):
				heapq.heappush(min_heap, j)
				heapq.heappush(max_heap, -j)
			current_max = i
			min_val.append(str(i))
			max_val.append(str(i))
		else:
			min_val.append(str(heapq.heappop(min_heap)))
			max_val.append(str(-heapq.heappop(max_heap)))
	return (' '.join(min_val), ' '.join(max_val))
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	arr = [int(i) for i in input().split()]
	(min_val, max_val) = get_min_max(arr, n)
	print(min_val)
	print(max_val)


from os import path
import sys, time
mod = int(1000000000.0 + 7)
from math import ceil, floor, gcd, log, log2, factorial, sqrt
from collections import defaultdict, Counter, OrderedDict, deque
from itertools import combinations, permutations
from bisect import *
from functools import reduce
from operator import mul
maxx = float('inf')
I = lambda : int(sys.stdin.buffer.readline())
lint = lambda : [int(x) for x in sys.stdin.buffer.readline().split()]
S = lambda : sys.stdin.readline().strip('\n')
grid = lambda r: [lint() for i in range(r)]
localsys = 0
start_time = time.time()
nCr = lambda n, r: reduce(mul, range(n - r + 1, n + 1), 1) // factorial(r)

def ceill(n, x):
	return (n + x - 1) // x
T = 1

def make_set(v):
	parent[v] = v

def find_set(v):
	if v == parent[v]:
		return v
	return find_set(parent[v])

def union_sets(a, b):
	a = find_set(a)
	b = find_set(b)
	if a != b:
		parent[b] = a

def lcs(x, y):
	(m, n) = (len(x), len(y))
	dp = [[None] * (n + 1) for _ in range(m + 1)]
	for i in range(m + 1):
		for j in range(n + 1):
			if i == 0 or j == 0:
				dp[i][j] = 0
			elif y[j - 1] == x[i - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
	return dp[m][n]

def solve():
	n = I()
	(a, mini, maxi, rem1, rem2, curr) = (lint(), [], [], deque(), deque(), 0)
	for i in a:
		if i == curr:
			maxi.append(rem1.pop())
			mini.append(rem2.popleft())
		else:
			for k in range(curr + 1, i):
				rem1.append(k)
				rem2.append(k)
			maxi.append(i)
			mini.append(i)
			curr = i
	print(*mini, '\n', *maxi)

def run():
	if path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
run()
T = I() if T else 1
for _ in range(T):
	solve()
if localsys:
	print('\n\nTime Elased :', time.time() - start_time, 'seconds')


from __future__ import division, print_function
import math
import os
import sys
from fractions import *
from sys import stdin, stdout
from io import BytesIO, IOBase
from itertools import accumulate
from collections import *
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def inpu():
	return int(inp())

def regularbracket(t):
	p = 0
	for i in t:
		if i == '(':
			p += 1
		else:
			p -= 1
		if p < 0:
			return False
	else:
		if p > 0:
			return False
		else:
			return True

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def reverse1(string):
	pp = ''
	for i in string[::-1]:
		pp += i
	if pp == string:
		return True
	return False

def reverse2(list1):
	l = []
	for i in list1[::-1]:
		l.append(i)
	if l == list1:
		return True
	return False

def mex(list1):
	p = max(list1) + 1
	for i in range(len(list1)):
		if list1[i] != i:
			p = i
			break
	return p

def sumofdigits(n):
	n = str(n)
	s1 = 0
	for i in n:
		s1 += int(i)
	return s1

def perfect_square(n):
	s = math.sqrt(n)
	if s == int(s):
		return True
	return False

def roman_number(x):
	if x > 15999:
		return
	value = [5000, 4000, 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
	symbol = ['F', 'MF', 'M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I']
	roman = ''
	i = 0
	while x > 0:
		div = x // value[i]
		x = x % value[i]
		while div:
			roman += symbol[i]
			div -= 1
		i += 1
	return roman

def soretd(s):
	for i in range(1, len(s)):
		if s[i - 1] > s[i]:
			return False
	return True

def countRhombi(h, w):
	ct = 0
	for i in range(2, h + 1, 2):
		for j in range(2, w + 1, 2):
			ct += (h - i + 1) * (w - j + 1)
	return ct

def countrhombi2(h, w):
	return h * h // 4 * (w * w // 4)

def binpow(a, b):
	if b == 0:
		return 1
	else:
		res = binpow(a, b // 2)
	if b % 2 != 0:
		return res * res * a
	else:
		return res * res

def binpowmodulus(a, b, m):
	a %= m
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % m
		a = a * a % m
		b >>= 1
	return res

def coprime_to_n(n):
	result = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			while n % i == 0:
				n //= i
			result -= result // i
		i += 1
	if n > 1:
		result -= result // n
	return result

def prime(x):
	if x == 1:
		return False
	else:
		for i in range(2, int(math.sqrt(x)) + 1):
			if x % i == 0:
				return False
		else:
			return True

def luckynumwithequalnumberoffourandseven(x, n, a):
	if x >= n and str(x).count('4') == str(x).count('7'):
		a.append(x)
	elif x < 1000000000000.0:
		luckynumwithequalnumberoffourandseven(x * 10 + 4, n, a)
		luckynumwithequalnumberoffourandseven(x * 10 + 7, n, a)
	return a

def luckynuber(x, n, a):
	p = set(str(x))
	if len(p) <= 2:
		a.append(x)
	if x < n:
		luckynuber(x + 1, n, a)
	return a
res = set()

def solve(p, l, a, b, n):
	if p > n or l > 10:
		return
	if p > 0:
		res.add(p)
	solve(p * 10 + a, l + 1, a, b, n)
	solve(p * 10 + b, l + 1, a, b, n)
from itertools import combinations

def main():
	t = inpu()
	for _ in range(t):
		n = inpu()
		arr = lis()
		q1 = deque()
		q2 = deque()
		ans1 = deque()
		ans2 = deque()
		prev = 0
		for i in range(n):
			if arr[i] == prev:
				ans1.append(q1.popleft())
				ans2.append(q2.pop())
			else:
				ans1.append(arr[i])
				ans2.append(arr[i])
				for j in range(prev + 1, arr[i]):
					q1.append(j)
					q2.append(j)
				prev = arr[i]
		print(*ans1)
		print(*ans2)
main()


from collections import deque
I = input
IN = lambda x: map(int, x.split())
L = lambda x: list(IN(x))
for _ in range(int(I())):
	n = int(I())
	q = L(I())
	mx = 0
	i = 0
	maxl = []
	reml = deque()
	remh = deque()
	minl = []
	while i < n:
		if q[i] > mx:
			for j in range(mx + 1, q[i]):
				reml.append(j)
				remh.append(j)
			mx = q[i]
			maxl += [mx]
			minl += [mx]
		else:
			maxl += [remh.pop()]
			minl += [reml.popleft()]
		i += 1
	print(*minl, '\n', *maxl)


import heapq
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	maxi = []
	mini = []
	maxHeap = []
	minHeap = []
	lastMax = 0
	visited = set()
	for (i, val) in enumerate(arr):
		if val not in visited:
			mini.append(val)
			maxi.append(val)
			for j in range(lastMax + 1, val):
				heapq.heappush(minHeap, j)
				heapq.heappush(maxHeap, -j)
			lastMax = val
		else:
			mini.append(heapq.heappop(minHeap))
			maxi.append(-heapq.heappop(maxHeap))
		visited.add(val)
	print(*mini)
	print(*maxi)


import sys
import heapq
from collections import Counter
import bisect

def load_sys():
	return sys.stdin.readlines()

def load_local():
	with open('input.txt', 'r') as f:
		input = f.readlines()
	return input

def f(n, arr):
	ans = [-1] * n
	seen = [False] * (n + 1)
	for i in range(n):
		if i == 0 or arr[i] != arr[i - 1]:
			ans[i] = arr[i]
			seen[arr[i]] = True
	mn = ans[:]
	mx = ans[:]
	pq = []
	mn_pq = []
	i = 0
	j = 0
	cur_mx = 1
	while i < n:
		lo = ans[i]
		i += 1
		i0 = i
		while i < n and ans[i] == -1:
			i += 1
		for x in range(cur_mx, lo, 1):
			if not seen[x]:
				heapq.heappush(pq, -x)
				heapq.heappush(mn_pq, x)
		ss = i - i0
		for _ in range(ss):
			mx[i0] = -heapq.heappop(pq)
			mn[i0] = heapq.heappop(mn_pq)
			i0 += 1
		cur_mx = lo
	return (mn, mx)
input = load_sys()
for i in range(1, len(input), 2):
	n = int(input[i])
	arr = [int(x) for x in input[i + 1].split()]
	(mn, mx) = f(n, arr)
	print(' '.join((str(x) for x in mn)))
	print(' '.join((str(x) for x in mx)))


import sys
input = sys.stdin.readline
for nt in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	minn = [0] * n
	minn[0] = a[0]
	for i in range(1, n):
		if a[i] != a[i - 1]:
			minn[i] = a[i]
	s = set(minn)
	curr = 1
	for i in range(n):
		if minn[i] == 0:
			while curr in s:
				curr += 1
			minn[i] = curr
			curr += 1
	print(*minn)
	maxx = [0] * n
	maxx[0] = a[0]
	for i in range(1, n):
		if a[i] != a[i - 1]:
			maxx[i] = a[i]
	s = set(maxx)
	curr = n
	left = []
	prev = 0
	for i in range(n):
		if maxx[i] == 0:
			maxx[i] = left.pop()
		else:
			for j in range(prev + 1, maxx[i]):
				left.append(j)
			prev = maxx[i]
	print(*maxx)


from sys import stdin, stdout
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	dic = {}
	for i in range(1, n + 1):
		dic[i] = 0
	lis = list(map(int, input().split()))
	min_lis = [0] * n
	prev = min_lis[0] = lis[0]
	dic[prev] = 1
	i = 0
	while i < n:
		if lis[i] > prev:
			prev = lis[i]
			min_lis[i] = prev
			dic[prev] = 1
		i += 1
	arr = [i for i in range(1, n + 1) if dic[i] == 0]
	arr2 = arr[:]
	max_lis = min_lis[:]
	i = 0
	for j in range(n):
		if min_lis[j] == 0:
			min_lis[j] = arr[i]
			i += 1
	print(*min_lis)
	stack = []
	i = 0
	while i < len(arr) - 1 and arr[i + 1] < max_lis[0]:
		i += 1
	last = i
	curr = i
	for i in range(n):
		if len(stack) > 0 and curr == stack[0][1]:
			curr = stack[0][0]
			stack.pop(0)
		if max_lis[i] == 0:
			max_lis[i] = arr[curr]
			curr -= 1
		elif last < len(arr) - 1 and max_lis[i] > arr[last + 1]:
			stack.insert(0, [curr, last])
			j = last + 1
			while j < len(arr) - 1 and arr[j + 1] < max_lis[i]:
				j += 1
			last = j
			curr = j
	print(*max_lis)


from collections import defaultdict, deque, Counter
from heapq import heapify, heappop, heappush
import math
from copy import deepcopy
from itertools import combinations, permutations, product
from bisect import bisect_left, bisect_right
import sys

def input():
	return sys.stdin.readline().rstrip()

def getN():
	return int(input())

def getNM():
	return map(int, input().split())

def getList():
	return list(map(int, input().split()))

def getArray(intn):
	return [int(input()) for i in range(intn)]
mod = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')
eps = 10 ** (-10)
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
T = getN()
for _ in range(T):
	N = getN()
	A = getList()
	l = [N - i for i in range(N)]
	(lower, upper) = ([-1] * N, [-1] * N)
	(low_que, up_que) = ([], [])
	now = 0
	for i in range(N):
		if i == 0 or A[i - 1] < A[i]:
			now = A[i]
			lower[i] = upper[i] = now
		while l and l[-1] <= now:
			u = l.pop()
			if u < now:
				heappush(low_que, u)
				heappush(up_que, -u)
		if lower[i] == -1:
			lower[i] = heappop(low_que)
			upper[i] = -heappop(up_que)
	print(*lower)
	print(*upper)


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
from collections import defaultdict
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree2:

	def __init__(self, data, default=3000006, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 10, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] > k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

class TrieNode:

	def __init__(self):
		self.children = [None] * 26
		self.isEndOfWord = False

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return TrieNode()

	def _charToIndex(self, ch):
		return ord(ch) - ord('a')

	def insert(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				pCrawl.children[index] = self.getNode()
			pCrawl = pCrawl.children[index]
		pCrawl.isEndOfWord = True

	def search(self, key):
		pCrawl = self.root
		length = len(key)
		for level in range(length):
			index = self._charToIndex(key[level])
			if not pCrawl.children[index]:
				return False
			pCrawl = pCrawl.children[index]
		return pCrawl != None and pCrawl.isEndOfWord

class Node:

	def __init__(self, data):
		self.data = data
		self.count = 0
		self.left = None
		self.right = None

class BinaryTrie:

	def __init__(self):
		self.root = Node(0)

	def insert(self, pre_xor, t):
		self.temp = self.root
		for i in range(31, -1, -1):
			val = pre_xor & 1 << i
			if val:
				if not self.temp.right:
					self.temp.right = Node(0)
				self.temp = self.temp.right
				self.temp.count += t
			if not val:
				if not self.temp.left:
					self.temp.left = Node(0)
				self.temp = self.temp.left
				self.temp.count += t
		self.temp.data = pre_xor

	def query(self, p, l):
		ans = 0
		self.temp = self.root
		for i in range(31, -1, -1):
			val = p & 1 << i
			val1 = l & 1 << i
			if val1 == 0:
				if val == 0:
					if self.temp.left and self.temp.left.count > 0:
						self.temp = self.temp.left
					else:
						return ans
				elif self.temp.right and self.temp.right.count > 0:
					self.temp = self.temp.right
				else:
					return ans
			elif val != 0:
				if self.temp.right:
					ans += self.temp.right.count
				if self.temp.left and self.temp.left.count > 0:
					self.temp = self.temp.left
				else:
					return ans
			else:
				if self.temp.left:
					ans += self.temp.left.count
				if self.temp.right and self.temp.right.count > 0:
					self.temp = self.temp.right
				else:
					return ans
		return ans
for ik in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = [0] * n
	ans1 = [0] * n
	ans[0] = l[0]
	ans1[0] = l[0]
	e = []
	e1 = []
	for i in range(1, l[0]):
		heapq.heappush(e, i)
		heapq.heappush(e1, -i)
	heapq.heapify(e)
	heapq.heapify(e1)
	for i in range(1, n):
		if l[i] == l[i - 1]:
			ans[i] = heapq.heappop(e)
			ans1[i] = -heapq.heappop(e1)
		else:
			for j in range(l[i - 1] + 1, l[i]):
				heapq.heappush(e, j)
				heapq.heappush(e1, -j)
			ans[i] = l[i]
			ans1[i] = l[i]
	print(*ans)
	print(*ans1)


t = int(input())
from collections import deque
for _ in range(t):
	n = int(input())
	arr = list(map(int, list(input().split())))
	cur = 0
	M_choice = deque([])
	m_choice = deque([])
	M = []
	m = []
	for i in range(n):
		if cur != arr[i]:
			for j in range(cur + 1, arr[i]):
				m_choice.append(j)
				M_choice.appendleft(j)
			cur = arr[i]
			m.append(cur)
			M.append(cur)
		else:
			m.append(m_choice.popleft())
			M.append(M_choice.popleft())
	print(*m)
	print(*M)


import bisect
import collections
import functools
import itertools
import math
import heapq
import random
import string

def repeat(_func=None, *, times=1):

	def decorator(func):

		@functools.wraps(func)
		def wrapper(*args, **kwargs):
			for _ in range(times):
				func(*args, **kwargs)
		return wrapper
	if _func is None:
		return decorator
	else:
		return decorator(_func)

def unpack(func=int):
	return map(func, input().split())

def l_unpack(func=int):
	return list(map(func, input().split()))

def getint():
	return int(input())

def getmatrix(rows):
	return [list(map(int, input().split())) for _ in range(rows)]

def display_matrix(mat):
	for i in range(len(mat)):
		print(mat[i])

def getmin(arr, n):
	output = [-1] * n
	vstd = [False] * (n + 1)
	vstd[arr[0]] = True
	output[0] = arr[0]
	hp = [x for x in range(1, arr[0])]
	heapq.heapify(hp)
	maxi = arr[0] - 1
	(heappush, heappop) = (heapq.heappush, heapq.heappop)
	for i in range(1, n):
		if arr[i] > arr[i - 1]:
			output[i] = arr[i]
			vstd[arr[i]] = True
			while maxi + 1 < arr[i]:
				maxi += 1
				if not vstd[maxi]:
					heappush(hp, maxi)
		else:
			while vstd[hp[0]]:
				heappop(hp)
			output[i] = heappop(hp)
			vstd[output[i]] = True
	return output

def getmax(arr, n):
	output = [-1] * n
	vstd = [False] * (n + 1)
	vstd[arr[0]] = True
	output[0] = arr[0]
	hp = [-x for x in range(1, arr[0])]
	heapq.heapify(hp)
	maxi = arr[0] - 1
	(heappush, heappop) = (heapq.heappush, heapq.heappop)
	for i in range(1, n):
		if arr[i] > arr[i - 1]:
			output[i] = arr[i]
			vstd[arr[i]] = True
			while maxi + 1 < arr[i]:
				maxi += 1
				if not vstd[maxi]:
					heappush(hp, -maxi)
		else:
			while vstd[-hp[0]]:
				heappop(hp)
			output[i] = -heappop(hp)
			vstd[output[i]] = True
	return output

@repeat(times=int(input()))
def main():
	n = getint()
	arr = l_unpack()
	lmin = getmin(arr, n)
	print(*lmin)
	lmax = getmax(arr, n)
	print(*lmax)
MOD = 10 ** 9 + 7
main()


from sys import stdin, stdout
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
from bisect import bisect, bisect_left
from time import time
from itertools import permutations as per
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
lcm = lambda x, y: x * y // gcd(x, y)
nCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N
inv = lambda x: pow(x, N - 2, N)
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7
for _ in range(I()):
	n = I()
	a = L()
	v = [i for i in range(n + 1)]
	p = [1] * (n + 1)
	for i in a:
		v[i] = i - 1
		p[i] = 0
	ans1 = a.copy()
	ans2 = a.copy()
	mx = -inf
	j = 1
	mx = -inf
	for i in range(1, n):
		if a[i] == a[i - 1]:
			while not p[j]:
				j += 1
			ans1[i] = j
			p[j] = 0
			k = a[i]
			while v[k] != k:
				v[k] = v[v[k]]
				k = v[k]
			ans2[i] = k
			v[k] = k - 1
	print(*ans1)
	print(*ans2)


import os
import sys
from io import BytesIO, IOBase

def solvemn(arr, v):
	l = 0
	for i in range(len(arr)):
		if arr[i] == 0:
			while v[l]:
				l += 1
			arr[i] = l
			l += 1
	return

def solvemx(arr, v):
	prev = arr[0]
	for i in range(1, len(arr)):
		if arr[i] == prev:
			l = prev
			while v[l]:
				l -= v[l]
			v[prev] = prev - l + 1
			arr[i] = l
		else:
			prev = arr[i]
	return

def main():
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		mn = [0] * n
		mn[0] = arr[0]
		vis = [0] * (n + 1)
		vis[mn[0]] = 1
		vis[0] = 1
		for i in range(1, n):
			if arr[i] == arr[i - 1]:
				continue
			mn[i] = arr[i]
			vis[arr[i]] = 1
		solvemn(mn, vis.copy())
		solvemx(arr, vis)
		print(*mn)
		print(*arr)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from heapq import heappush, heappop
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	maximal = [0] * n
	minimal = [0] * n
	minrem = []
	maxrem = []
	last = 0
	for i in range(n):
		if a[i] == last:
			maximal[i] = -heappop(maxrem)
			minimal[i] = heappop(minrem)
		else:
			(maximal[i], minimal[i]) = (a[i], a[i])
			for j in range(last + 1, a[i]):
				heappush(maxrem, -j)
				heappush(minrem, j)
			last = a[i]
	print(*minimal)
	print(*maximal)


import os, sys
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import bisect_left, bisect_right
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
import heapq as h, time
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def getInt():
	return int(input())

def getStrs():
	return input().split()

def getInts():
	return list(map(int, input().split()))

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def getBin():
	return list(map(int, list(input())))

def isInt(s):
	return '0' <= s[0] <= '9'

def ceil_(a, b):
	return a // b + (a % b > 0)
MOD = 10 ** 9 + 7

def solve():
	N = getInt()
	A = getInts()
	free1 = []
	free2 = []
	ans1 = [0] * N
	ans2 = [0] * N
	h.heapify(free1)
	h.heapify(free2)
	prev = 0
	for i in range(N):
		if A[i] > prev:
			ans1[i] = A[i]
			ans2[i] = A[i]
			for j in range(prev + 1, A[i]):
				h.heappush(free1, j)
				h.heappush(free2, -j)
			prev = A[i]
		else:
			y = h.heappop(free1)
			z = -h.heappop(free2)
			ans1[i] = y
			ans2[i] = z
	print(*ans1)
	print(*ans2)
	return
for _ in range(getInt()):
	solve()


def solve():
	n = int(input())
	q = [int(x) for x in input().split()]
	amin = []
	used = [False for _ in range(n + 1)]
	l = 1
	for i in range(n):
		if i == 0 or q[i] > q[i - 1]:
			amin.append(q[i])
			used[q[i]] = True
		else:
			while used[l]:
				l += 1
			amin.append(l)
			l += 1
	amax = []
	l = 1
	z = []
	for i in range(n):
		if i == 0 or q[i] > q[i - 1]:
			while l <= q[i]:
				z.append(l)
				l += 1
		amax.append(z.pop())
	print(*amin)
	print(*amax)
t = int(input())
for _ in range(t):
	solve()


from collections import deque
for i in range(int(input())):
	x = int(input())
	massiv = list(map(int, input().split()))
	min_x = []
	max_x = []
	maxs = 0
	ochered_min = deque()
	ochered_max = deque()
	for j in massiv:
		if j > maxs:
			for k in range(maxs + 1, j):
				ochered_min.append(k)
				ochered_max.append(k)
			maxs = j
			min_x.append(maxs)
			max_x.append(maxs)
		else:
			min_x.append(ochered_min.popleft())
			max_x.append(ochered_max.pop())
	print(*min_x)
	print(*max_x)


import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	vis = [0] * (n + 1)
	vis[a[0]] = 1
	for i in range(1, n):
		if a[i] != a[i - 1]:
			vis[a[i]] = 1
	mini = [a[0]]
	maxi = [a[0]]
	available = []
	for i in range(1, n + 1):
		if vis[i] == 0:
			available.append(i)
	available.reverse()
	for i in range(1, n):
		if a[i] == a[i - 1]:
			mini.append(available.pop())
		else:
			mini.append(a[i])
	available = []
	for i in range(1, a[0]):
		available.append(i)
	prev = a[0]
	for i in range(1, n):
		if a[i] == a[i - 1]:
			maxi.append(available.pop())
		else:
			for j in range(prev + 1, a[i]):
				available.append(j)
			prev = a[i]
			maxi.append(a[i])
	print(*mini)
	print(*maxi)


for _ in range(int(input())):
	n = int(input())
	q = list(map(int, input().split()))
	mn = [0] * n
	mx = [0] * n
	used = [0] * (n + 1)
	mn[0] = q[0]
	mx[0] = q[0]
	used[q[0]] = 1
	for i in range(1, n):
		if q[i] != q[i - 1]:
			mn[i] = q[i]
			mx[i] = q[i]
			used[q[i]] = 1
	k = 1
	for i in range(n):
		if mn[i] == 0:
			while used[k]:
				k += 1
			mn[i] = k
			k += 1
	st = [0] * n
	j = 0
	k = 1
	for i in range(n):
		if mx[i] == 0:
			while k <= q[i]:
				if used[k] == 0:
					st[j] = k
					j += 1
				k += 1
			mx[i] = st[j - 1]
			j -= 1
	for i in mn:
		print(i, end=' ')
	print()
	for j in mx:
		print(j, end=' ')
	print()


import bisect
for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	s_t = set(s)
	st = list((i for i in range(1, n + 1) if i not in s_t))
	ar = [s[0]] + [0 for i in range(n - 1)]
	for i in range(1, n):
		if s[i] != s[i - 1]:
			ar[i] = s[i]
	st1 = st
	st2 = st
	ar1 = ar.copy()
	x = 0
	for i in range(n):
		if ar1[i] == 0:
			ar1[i] = st1[x]
			x += 1
	print(*ar1)
	for i in range(1, n):
		if ar[i] == 0:
			pos = bisect.bisect_left(st2, ar[i - 1])
			if pos == 0:
				ar[i] = st2[pos + 1]
				st2.pop(pos - 1)
			else:
				ar[i] = st2[pos - 1]
				st2.pop(pos - 1)
	print(*ar)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	used = set(a)
	k = 1
	print(a[0], end=' ')
	for i in range(1, n):
		if a[i] != a[i - 1]:
			print(a[i], end=' ')
			continue
		while k in used:
			k += 1
		print(k, end=' ')
		k += 1
	print()
	print(a[0], end=' ')
	connect = {a[0]: a[0] - 1}
	for i in range(1, n):
		if a[i] != a[i - 1]:
			print(a[i], end=' ')
			if a[i] - 1 in connect:
				connect[a[i]] = connect[a[i] - 1]
			else:
				connect[a[i]] = a[i] - 1
			continue
		print(connect[a[i]], end=' ')
		if connect[a[i]] - 1 in connect:
			connect[a[i]] = connect[connect[a[i]] - 1]
		else:
			connect[a[i]] -= 1
	print()


from collections import deque
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(minq, maxq) = (deque([]), deque([]))
	(minarr, maxarr) = ([], [])
	maxSeen = 0
	for i in range(n):
		already = arr[i] == maxSeen
		while maxSeen < arr[i]:
			maxSeen += 1
			minq.append(maxSeen)
			maxq.append(maxSeen)
		if already:
			minarr.append(minq.popleft())
			maxarr.append(maxq.pop())
		else:
			minarr.append(minq.pop())
			maxarr.append(maxq.pop())
	print(*minarr)
	print(*maxarr)


from sys import stdin, stdout
stdin.readline

def mp():
	return list(map(int, stdin.readline().strip().split()))

def it():
	return int(stdin.readline().strip())
from collections import defaultdict as dd, Counter as C, deque
from math import ceil
for _ in range(it()):
	n = it()
	l = mp()
	vmi = deque([])
	vma = []
	for i in range(1, l[0]):
		vmi.append(i)
		vma.append(i)
	(ma, mi) = ([l[0]], [l[0]])
	for i in range(1, n):
		if l[i] == l[i - 1]:
			k = vma.pop()
			ma.append(k)
		else:
			for j in range(l[i - 1] + 1, l[i]):
				vma.append(j)
			ma.append(l[i])
	for i in range(1, n):
		if l[i] == l[i - 1]:
			k = vmi.popleft()
			mi.append(k)
		else:
			for j in range(l[i - 1] + 1, l[i]):
				vmi.append(j)
			mi.append(l[i])
	print(*mi)
	print(*ma)


class Queue:
	stack1 = []
	stack2 = []

	def add(self, el):
		self.stack1.append(el)

	def pop(self):
		if self.stack2:
			return self.stack2.pop()
		else:
			length = len(self.stack1)
			for i in range(length):
				self.stack2.append(self.stack1.pop())
			return self.stack2.pop()

def permute(list_num):
	min_mem = Queue()
	for el in range(1, list_num[0]):
		min_mem.add(el)
	min_perm = [list_num[0]]
	max_mem = [el for el in range(1, list_num[0])]
	max_perm = [list_num[0]]
	for i in range(1, len(list_num)):
		if list_num[i] == list_num[i - 1]:
			val = min_mem.pop()
			min_perm.append(val)
			val = max_mem.pop()
			max_perm.append(val)
		else:
			min_perm.append(list_num[i])
			max_perm.append(list_num[i])
			for el in range(list_num[i - 1] + 1, list_num[i]):
				min_mem.add(el)
				max_mem.append(el)
	print(*min_perm)
	print(*max_perm)
num = int(input())
for i in range(num):
	s = input()
	list_num = [int(el) for el in input().split()]
	permute(list_num)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	b = l.copy()
	d = {l[0]: 0}
	ans = [l[0]]
	a = []
	for i in range(1, n):
		d.setdefault(l[i], i)
		if b[i] == b[i - 1]:
			l[i] = 'X'
		else:
			ans.append(l[i])
	for i in range(1, n + 1):
		d.setdefault(i, -1)
		if d[i] == -1:
			a.append(i)
	ans1 = l.copy()
	i = 0
	k = 0
	while i < len(ans):
		j = d[ans[i]] + 1
		if j < n:
			while ans1[j] == 'X':
				ans1[j] = a[k]
				k += 1
				j += 1
				if j == n:
					break
		i += 1
	k = 1
	ans2 = l.copy()
	i = 0
	s = []
	while i < len(ans):
		j = d[ans[i]] + 1
		if j < n:
			while ans2[j] == 'X':
				while k < ans[i]:
					if d[k] == -1:
						s.append(k)
						d[k] = -2
					k += 1
				ans2[j] = s.pop()
				j += 1
				if j == n:
					break
		i += 1
	print(*ans1)
	print(*ans2)


from collections import deque
cas = int(input())
while cas:
	cas -= 1
	n = int(input())
	a = list(map(int, input().split()))
	ans1 = []
	tmp1 = deque()
	ans2 = []
	tmp2 = deque()
	for i in range(n):
		if i == 0:
			for j in range(1, a[i]):
				tmp1.append(j)
				tmp2.append(j)
			ans1.append(a[i])
			ans2.append(a[i])
		elif a[i] != a[i - 1]:
			for j in range(a[i - 1] + 1, a[i]):
				tmp1.append(j)
				tmp2.append(j)
			ans1.append(a[i])
			ans2.append(a[i])
		else:
			ans1.append(tmp1.pop())
			ans2.append(tmp2.popleft())
	for i in range(n):
		if i == n - 1:
			print(ans2[i])
		else:
			print(ans2[i], end=' ')
	for i in range(n):
		if i == n - 1:
			print(ans1[i])
		else:
			print(ans1[i], end=' ')


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():

	def update(ind):
		ind += n
		segment[ind] = -INF
		while ind > 1:
			ind >>= 1
			segment[ind] = max(segment[2 * ind], segment[2 * ind + 1])

	def getMax(a, b):
		a += n
		b += n
		s = -INF
		while a <= b:
			if a % 2:
				s = max(s, segment[a])
				a += 1
			if b % 2 == 0:
				s = max(s, segment[b])
				b -= 1
			b >>= 1
			a >>= 1
		update(s - 1)
		return s
	n = inp()
	l = li()
	ma = [0]
	segment = [0]
	ans1 = []
	for i in range(n):
		ma.append(0)
		segment.append(0)
		ans1.append(0)
	segment = segment + segment
	for i in range(n):
		segment[i + n] = i + 1
	for i in range(n - 1, 0, -1):
		segment[i] = max(segment[2 * i], segment[2 * i + 1])
	ans2 = list(ans1)
	ma[l[0]] = 1
	ans1[0] = l[0]
	ans2[0] = l[0]
	i = 1
	update(l[0] - 1)
	while i < n:
		if l[i] > l[i - 1]:
			ma[l[i]] = 1
			update(l[i] - 1)
			ans2[i] = l[i]
			ans1[i] = l[i]
		i += 1
	j = 1
	for i in range(n):
		if ans1[i] == 0:
			while j < n and ma[j] == 1:
				j += 1
			ans1[i] = j
			ma[j] = 1
	for i in range(n):
		if ans2[i] != 0:
			now = ans2[i]
		elif ans2[i] == 0:
			last = getMax(0, now - 1)
			ans2[i] = last
	print(*ans1)
	print(*ans2)
for _ in range(inp()):
	solve()


from collections import deque
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a = [0] + a
	minimal = []
	maximal = []
	s = deque([])
	for i in range(1, len(a)):
		if a[i] != a[i - 1]:
			maximal.append(a[i])
			for j in range(a[i - 1] + 1, a[i]):
				s.appendleft(j)
		else:
			maximal.append(s.popleft())
	s = deque([])
	for i in range(1, len(a)):
		if a[i] != a[i - 1]:
			minimal.append(a[i])
			for j in range(a[i - 1] + 1, a[i]):
				s.append(j)
		else:
			minimal.append(s.popleft())
	print(*minimal)
	print(*maximal)


import collections
import heapq

def mnp(n, q):
	res = []
	taken = [0] * (n + 1)
	last = None
	missed = 1
	for i in range(n):
		if q[i] != last:
			taken[q[i]] = 1
			res.append(q[i])
		else:
			while taken[missed] != 0:
				missed += 1
			taken[missed] = 1
			res.append(missed)
			missed += 1
		last = q[i]
	return res

def mxp(n, q):
	res = []
	taken = [0] * (n + 1)
	last = None
	heap = []
	missed = 1
	for i in range(n):
		if q[i] != last:
			taken[q[i]] = 1
			res.append(q[i])
			while missed < q[i]:
				if taken[missed] == 0:
					heapq.heappush(heap, -missed)
				missed += 1
		else:
			v = heapq.heappop(heap)
			taken[-v] = 1
			res.append(-v)
		last = q[i]
	return res

def process(n, q):
	print(' '.join(map(str, mnp(n, q))))
	print(' '.join(map(str, mxp(n, q))))
tcs = int(input())
for tc in range(tcs):
	n = int(input())
	q = list(map(int, input().split()))
	process(n, q)


def mingrid():
	for _ in range(int(input())):
		n = int(input())
		segcost = input().split()
		minodd = int(segcost[0])
		mineven = int(segcost[1])
		sumodd = minodd
		sumeven = mineven
		codd = 1
		ceven = 1
		res = sumodd + minodd * (n - codd) + sumeven + mineven * (n - ceven)
		for i in range(2, n):
			now = int(segcost[i])
			if (i + 1) % 2:
				minodd = min(minodd, now)
				sumodd += now
				codd += 1
			else:
				mineven = min(mineven, now)
				sumeven += now
				ceven += 1
			res = min(res, sumodd + minodd * (n - codd) + sumeven + mineven * (n - ceven))
		print(res)

def numofpairs():
	n = (10 * 2) ** 7 + 1
	l = [False] * n
	primes = []
	for i in range(2, n):
		if not l[i]:
			for i1 in range(i + i, n, i):
				l[i1] = True
			primes.append(i)
			l[i] = True
	tol = [0, 0]
	for i in range(2, n):
		pos = 0
		t = 0
		while i:
			val = primes[pos]
			if not i:
				tol.append(t)
				break
			elif i < val:
				tol.append(t + 1)
				break
			elif not i % val:
				i //= val
			else:
				pos += 1
				t += 1
	for _ in range(int(input())):
		(c, d, x) = map(int, input().split())
		lim = int(math.sqrt(x)) + 1
		ans = 0
		for i in range(1, lim):
			thing = i + d
			if thing % c:
				continue
			ans += 2 ** tol[thing // c]
		print(ans)

def restoremod():
	for _ in range(int(input())):
		length = int(input()) - 1
		l = input().split()
		t = False
		ife = False
		for i in range(length):
			if int(l[i]) == int(l[i + 1]):
				if i > 0:
					print(-1)
					t = True
					break
				else:
					ife = True
			elif ife:
				print(-1)
				t = True
				break
		if not t:
			posc = 0
			negc = 0
			res = int(l[1]) - int(l[0])
			if res > 0:
				posc = res
			else:
				negc = res
			if not negc:
				for i in range(1, length):
					now = int(l[i]) - int(l[i + 1])
					if now > 0:
						negc = now
						break
			if not posc:
				for i in range(1, length):
					change = int(l[i + 1]) - int(l[i])
					if change > 0:
						posc = change
						break
			if posc and negc:
				mod = posc + negc
			else:
				mod = 0
			c = posc if posc else -negc
			larnum = 0
			for i in range(length):
				nowi = int(l[i])
				larnum = max(larnum, nowi)
				if larnum > mod and mod:
					print(-1)
					t = True
					break
				res = int(l[i + 1]) - nowi
				if res < 0:
					if res != -(mod - c):
						print(-1)
						t = True
						break
				if res > 0:
					if res != c:
						t = True
						print(-1)
						break
			if not t:
				if mod:
					print(mod, c, sep=' ')
				else:
					print(mod)

def restoremod1():
	for _ in range(int(input())):
		num = int(input())
		...

def cells():
	for _ in range(int(input())):
		(row, col, num) = map(int, input().split())
		nr = (num - 1) % row
		nc = (num - 1) // row + 1
		print(nr * col + nc)

def replacement():
	for _ in range(int(input())):
		(l, k) = map(int, input().split())
		s = input()
		(left, righ) = (s.find('*'), s.rfind('*'))
		if righ - left <= k:
			print(2 if righ != left else 1)
		else:
			pos = left
			c = 2
			while righ - pos > k:
				pos = pos + k
				while pos < l and s[pos] != '*':
					pos -= 1
				c += 1
			print(c)
import math
import sys
input = sys.stdin.readline

def string():
	for _ in range(int(input())):
		s = input().rstrip()
		s1 = input().rstrip()
		maxl = 0
		p1 = [0, 0]
		p = [0, 0]
		for i in range(len(s)):
			for i1 in range(i + 1, len(s) + 1):
				pos = s1.find(s[i:i1])
				if pos == -1:
					break
				elif i1 - i <= maxl:
					continue
				elif i1 - i > maxl:
					maxl = i1 - i
					p1 = [pos, pos + maxl]
					p = [i, i + maxl]
		print(p[0] + len(s) - p[1] + (p1[0] + len(s1) - p1[1]) if maxl else len(s) + len(s1))
import collections

def trans(l):
	pos = 0
	while pos < len(l) - 1:
		avg = l[pos] // (len(l) - pos - 1)
		rem = l[pos] % (len(l) - pos - 1)
		l[pos] = 0
		for i in range(pos + 1, len(l)):
			l[i] -= avg
			if l[i] < 0:
				rem += -l[i]
				l[i] = 0
		while pos + 1 < len(l) and l[pos + 1] <= rem:
			rem -= l.pop(pos + 1)
		if pos + 1 < len(l):
			l[pos + 1] -= rem
		else:
			l[0] = rem
		pos += 1
	return sum(l)

def trans1(l):
	pos = 0
	lenl = len(l)
	pos1 = pos + 1
	while pos1 < lenl and pos < lenl:
		while pos1 < lenl and l[pos] - l[pos1] >= 0:
			l[pos] -= l[pos1]
			l[pos1] = 0
			pos1 += 1
		if pos1 < lenl:
			l[pos1] -= l[pos]
			l[pos] = 0
			pos = pos1
			pos1 += 1
	return sum(l)

def main():
	for _ in range(int(input())):
		num = input()
		l = sorted(list(collections.Counter(input().split()).values()), reverse=True)
		ans = trans(l[:])
		if ans:
			print(min(ans, trans1(l)))
		else:
			print(0)

def transrep():
	for _ in range(int(input())):
		num = int(input())
		l = list(collections.Counter(input().split()).values())
		ml = max(l)
		if ml > num - ml:
			print(ml - num + ml)
		else:
			print(num % 2)

def resmod():

	def solve():
		posc = -1
		negc = 1
		num = int(input())
		l = input().split()
		ifz = False
		maxi = int(l[0])
		for i in range(num - 1):
			maxi = max(maxi, int(l[i + 1]))
			c = int(l[i + 1]) - int(l[i])
			if c == 0:
				if not i:
					ifz = True
					continue
				elif not ifz:
					return -1
			elif ifz:
				return -1
			elif c < 0:
				if negc == 1:
					negc = c
				elif negc != c:
					return -1
			elif c > 0:
				if posc == -1:
					posc = c
				elif posc != c:
					return -1
		if posc == -1 or negc == 1:
			return 0
		mod = posc + -negc
		if mod <= maxi:
			return -1
		return '{0} {1}'.format(mod, posc)
	for _ in range(int(input())):
		print(solve())

def basicdep():

	def findmax(l):
		ans = 0
		res = 0
		for (i, v) in enumerate(l):
			if ans < v:
				res = i
				ans = v
		return [res + 1, ans]

	def roundup(num):
		s = num / 2
		if s != int(s):
			return int(s) + 1
		return int(s)
	for _ in range(int(input())):
		days = []
		(f, d) = map(int, input().split())
		friends = [0] * f
		for i in range(d):
			nowfs = input().split()
			nowff = int(nowfs[1])
			friends[nowff - 1] += 1
			if int(nowfs[0]) > 1:
				days.append([nowff, int(nowfs[2])])
			else:
				days.append([nowff, []])
		maxl = findmax(friends)
		goal = roundup(d)
		if maxl[1] < goal:
			print('YES')
			print(*[i[0] for i in days], sep=' ')
		else:
			pos = 0
			while pos < d and maxl[1] > goal:
				if days[pos][0] == maxl[0] and days[pos][1]:
					days[pos][0] = days[pos][1]
					maxl[1] -= 1
				pos += 1
			if maxl[1] > goal:
				print('NO')
			else:
				print('YES')
				print(*[i[0] for i in days], sep=' ')

def playlist():

	def nextsong(pos):
		while pos + 1 in ans and len(ans) != num:
			pos += 1
			if pos == num:
				pos = 0
		return pos

	def gcf(n, n1):
		if not n:
			return n1
		return gcf(n1, n % n1) if n1 else n
	for _ in range(int(input())):
		num = int(input())
		l = input().split()
		deletel = collections.deque()
		for i in range(num - 1):
			(a, b) = (int(l[i]), int(l[i + 1]))
			if gcf(a, b) == 1:
				deletel.append((i, i + 1))
		if gcf(int(l[-1]), int(l[0])) == 1:
			deletel.append((num - 1, 0))
		ans = dict()
		while deletel and len(ans) != num:
			(a, b) = deletel.popleft()
			if a + 1 in ans or b + 1 in ans:
				continue
			ans[b + 1] = True
			if deletel:
				if deletel[0][0] == b:
					deletel.popleft()
			if b == num - 1:
				n = nextsong(0)
				if gcf(int(l[a]), int(l[n])) == 1:
					deletel.append((a, n))
			else:
				n = nextsong(b + 1)
				if gcf(int(l[a]), int(l[n])) == 1:
					deletel.append((a, n))
		print(len(ans), *ans.keys(), sep=' ')

def shoesandst():
	(students, laces) = map(int, input().split())
	d = collections.defaultdict(list)
	rems = set()
	for _ in range(laces):
		(a, b) = map(int, input().split())
		d[a].append(b)
		d[b].append(a)
		lisa = d[a]
		lisb = d[b]
		la = len(lisa)
		lb = len(lisb)
		if la == 2:
			rems.discard((a, lisa[0]))
		elif la == 1:
			rems.add((a, b))
		if lb == 2:
			rems.discard((b, lisb[0]))
		elif lb == 1:
			rems.add((b, a))
	c = 0
	nextans = set()
	while rems or nextans:
		nextans.clear()
		while rems:
			(a, b) = rems.pop()
			nextans.discard((a, b))
			nextans.discard((b, a))
			d[a].pop()
			d[b].remove(a)
			lb = len(d[b])
			if not lb:
				rems.discard((b, a))
			if lb == 1:
				nextans.add((b, d[b][0]))
		rems = nextans.copy()
		c += 1
	return c
import heapq

def restoreperm():
	for _ in range(int(input())):
		length = int(input())
		maxselect = []
		minselect = []
		ansma = []
		ansmi = []
		last = 0
		for i in input().split():
			i = int(i)
			if i == last:
				ansma.append(-heapq.heappop(maxselect))
				ansmi.append(heapq.heappop(minselect))
			else:
				ansma.append(i)
				ansmi.append(i)
				for num in range(last + 1, i):
					heapq.heappush(maxselect, -num)
					heapq.heappush(minselect, num)
				last = i
		print(*ansmi, sep=' ')
		print(*ansma, sep=' ')
restoreperm()


import bisect
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	temp = list(arr)
	val = [i for i in range(1, n + 1)]
	s = set(arr)
	x = set(val)
	elem = list(x - s)
	flag = 0
	ind_val = temp[0]
	for i in range(1, n):
		if temp[i] == ind_val:
			temp[i] = elem[flag]
			flag += 1
		else:
			ind_val = temp[i]
	ind_val = arr[0]
	for i in range(1, n):
		if arr[i] == ind_val:
			el = bisect.bisect_left(elem, arr[i]) - 1
			arr[i] = elem[el]
			elem.pop(el)
		else:
			ind_val = arr[i]
	print(*temp)
	print(*arr)


from collections import deque
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	(minn, maxx, a, p1, p2) = (deque(), deque(), 0, [], [])
	for i in range(len(l)):
		c = l[i]
		if a == c:
			p1.append(minn.popleft())
			p2.append(maxx.pop())
		else:
			p1.append(c)
			p2.append(c)
			for i in range(a + 1, c):
				minn.append(i)
				maxx.append(i)
			a = c
	print(*p1)
	print(*p2)


import math
import heapq

def S():
	return input()

def M():
	return map(int, input().split())

def I():
	return int(S())

def L():
	return list(M())
for _ in range(I()):
	n = I()
	l = L()
	(s, sr) = ([], [])
	(h, hr) = ([], [])
	t = 0
	for i in range(n):
		if i == 0:
			s.append(l[i])
			h.append(l[i])
			for j in range(1, l[i]):
				sr.append(j)
				hr.append(j)
		elif l[i - 1] == l[i]:
			s.append(sr[t])
			t += 1
			h.append(hr[-1])
			hr.pop(-1)
		else:
			s.append(l[i])
			h.append(l[i])
			for j in range(l[i - 1] + 1, l[i]):
				sr.append(j)
				hr.append(j)
	print(*s)
	print(*h)