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

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

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;