#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 200005
#define maxm 200005
#define INF 1234567890
#define eps 1e-15
#define p 1000000007
const double pi=acos(-1);
template<class T>inline bool read(T &x)
{
    x=0;register char c=getchar();register bool f=0;
    while(!isdigit(c)){if(c==EOF)return false;f^=c=='-',c=getchar();}
    while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    if(f)x=-x;
    return true;
}
template<class T>inline void print(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10^48);
}
template<class T>inline void print(T x,char c){print(x),putchar(c);}
template<class T,class ...S>inline bool read(T &x,S &...y){return read(x)&&read(y...);}
ll T,n,a[maxn],b[maxn],x[maxn],mx,nxt[maxn],pre[maxn],l;
bool vis[maxn];
int main()
{
    //freopen("test.in","r",stdin);
    read(T);
    while(T--)
    {
        read(n);
        for(ll i=1;i<=n;i++)
        {
            read(x[i]);
            vis[i]=0;
        }
        for(ll i=0;i<=n;i++)nxt[i]=i+1;
        for(ll i=1;i<=n+1;i++)pre[i]=i-1;
        mx=0;
        l=1;
        for(ll i=1;i<=n;i++)
        {
            if(x[i]>mx)
            {
                a[i]=x[i];
                mx=max(mx,x[i]);
                vis[x[i]]=1;
            }
            else
            {
                for(ll j=l;j<=n;j++)
                {
                    if(!vis[j])
                    {
                        a[i]=j;
                        l=j+1;
                        break;
                    }
                }
            }
        }
        for(ll i=0;i<=n;i++)nxt[i]=i+1;
        for(ll i=1;i<=n+1;i++)pre[i]=i-1;
        mx=0;
        for(ll i=1;i<=n;i++)
        {
            if(x[i]>mx)
            {
                b[i]=x[i];
                mx=max(mx,x[i]);
                nxt[pre[x[i]]]=nxt[x[i]];
                pre[nxt[x[i]]]=pre[x[i]];
            }
            else
            {
                b[i]=pre[x[i]];
                nxt[pre[pre[x[i]]]]=nxt[pre[x[i]]];
                pre[nxt[pre[x[i]]]]=pre[pre[x[i]]];
                pre[x[i]]=pre[pre[x[i]]];
            }
        }
        for(ll i=1;i<=n;i++)print(a[i]," \n"[i==n]);
        for(ll i=1;i<=n;i++)print(b[i]," \n"[i==n]);
    }
    return 0;
}
