#include <bits/stdc++.h>
using namespace std;
#define PRINT(x) if(debug) {cout << #x << ": " << x << endl;}
#define PRINTARR(x) if (debug) {cout<<#x<<": ";for(auto i:x){cout<<i<<' ';}cout<<endl;}
#define ABS(x) ((x>=0)?x:-1*(x))
#define divideCeil(a,b) ((a+b-1) / b)
#define INF 1000000007
#define EPS 1e-9
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

bool debug;

int main(int argc, char *argv[]){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    debug = argc > 1;

    int t, n;
    cin >> t;
    while(t--){
        cin >> n;
        vi arr(n+1, 0);
        vi arrMin(n+1, -1), arrMax(n+1, -1);
        vector<bool> mark(n+1, false);
        for (int i=1; i<=n; i++){
            cin >> arr[i];
            if (arr[i] != arr[i-1]){
                arrMin[i] = arrMax[i] = arr[i]; 
                mark[arr[i]] = true;
            }
        }
        vi sisa;
        for (int i = 1; i <= n; i++)
        {
            if(!mark[i]){
                sisa.push_back(i);
            }
        }
        
        PRINTARR(arrMin)
        PRINTARR(arrMax)
        PRINTARR(sisa)

        int idx = 0;
        for (int i = 1; i <= n; i++)
        {
            if (arrMin[i] == -1){
                arrMin[i] = sisa[idx++];
            }
        }
        
        for (int i = 1; i <= n; i++)
        {
            cout << arrMin[i] << ' ';
        } cout << endl;

        priority_queue<int> pq;
        idx = 0;
        for (int i = 1; i <= n; i++)
        {
            if (arrMax[i] == -1){
                while(idx<sisa.size() && sisa[idx] < arr[i]){
                    pq.push(sisa[idx++]);
                }
                arrMax[i] = pq.top(); pq.pop();
            }
        }
        for (int i = 1; i <= n; i++)
        {
            cout << arrMax[i] << ' ';
        } cout << endl;
    }
    
    //cout << n << endl;

    return 0;
}