human
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, …, 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 ≤ i ≤ 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 ≤ t ≤ 10^4). Then t test cases follow.

The first line of each test case contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5).

The second line of each test case contains n integers q_1, q_2, …, q_n (1 ≤ q_i ≤ 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 ⋅ 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...
Using python3 can you solve the prior task?

Write me a Python program to find the lexicographically minimal and lexicographically maximal permutations that could have been originally presented to Polycarp?
assistant
#Here is Python program to find the lexicographically minimal and lexicographically maximal permutations that could have been originally presented to Polycarp.

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):
    """list unpack"""
    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()