CF1506E.Restoring the Permutation

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.

排列是指由 $1$ 到 $n$ 的 $n$ 个整数组成的序列，其中每个数字恰好出现一次。例如，$[1]$、$[3, 5, 2, 1, 4]$、$[1, 3, 2]$ 是排列，而 $[2, 3, 2]$、$[4, 3, 1]$、$[0]$ 不是。

波利卡普收到了一个由 $1$ 到 $n$ 构成的排列 $p$。然而，当他回到家时，发现口袋里的排列 $p$ 已根据如下规则变为数组 $q$：

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

现在波利卡普想知道：最初可能呈现给他的字典序最小和字典序最大的排列分别是什么？

长度为 $n$ 的数组 $a$ 在字典序上小于长度为 $n$ 的数组 $b$，当且仅当存在某个下标 $i$（$1 \le i \le n$），使得数组 $a$ 和 $b$ 的前 $i-1$ 个元素完全相同，且数组 $a$ 的第 $i$ 个元素小于数组 $b$ 的第 $i$ 个元素。例如，数组 $a=[1, 3, 2, 3]$ 在字典序上小于数组 $b=[1, 3, 4, 2]$。

例如，若 $n=7$ 且 $p=[3, 2, 4, 1, 7, 5, 6]$，则 $q=[3, 3, 4, 4, 7, 7, 7]$，而以下排列均可能是最初的 $p$：

• $[3, 1, 4, 2, 7, 5, 6]$（字典序最小的排列）；
• $[3, 1, 4, 2, 7, 6, 5]$；
• $[3, 2, 4, 1, 7, 5, 6]$；
• $[3, 2, 4, 1, 7, 6, 5]$（字典序最大的排列）。

对于给定的数组 $q$，请找出可能最初呈现给波利卡普的字典序最小和字典序最大的排列。

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$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）。随后是 $t$ 组测试数据。

每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。

每组测试数据的第二行包含 $n$ 个整数 $q_1, q_2, \ldots, q_n$（$1 \le q_i \le n$）。

保证数组 $q$ 是通过对某个排列 $p$ 应用题目描述中的规则得到的。

保证所有测试数据的 $n$ 之和不超过 $2 \cdot 10^5$。

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;

对于每个测试用例，输出两行：

• 第一行输出 $n$ 个整数——字典序最小的、可能最初提供给 Polycarp 的排列；
• 第二行输出 $n$ 个整数——字典序最大的、可能最初提供给 Polycarp 的排列；