#include <bits/stdc++.h>
using namespace std;

#define FAST_IO  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define show(x)  cerr << #x << " = " << x << '\n'
#define endl     '\n'
typedef long long ll;
typedef unsigned long long ull;
const double EPS = 1e-10;  // epsilon
const double PI = acos(-1);
const ll MOD = (ll)1e9 + 7;
const int N = 2e5 + 5;

int t = 1, n, a[N];
set<int> st;

vector<int> minimalPermutation();
vector<int> maximalPermutation();

int main()
{
    FAST_IO
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        auto ans1 = minimalPermutation();
        auto ans2 = maximalPermutation();
        for(auto x : ans1)cout << x << ' '; cout << "\n";
        for(auto x : ans2)cout << x << ' '; cout << "\n";
    }
    return 0;
}

vector<int> minimalPermutation()
{
    st.clear();
    for (int i = 1; i <= n; i++)
        st.insert(i);
    vector<int> ans;
    ans.push_back(a[0]);
    st.erase(a[0]);
    for (int i = 1; i < n; i++)
    {
        if(a[i] != a[i - 1])
        {
            st.erase(a[i]);
            ans.push_back(a[i]);
        }
        else 
        {
            auto it = st.begin();
            ans.push_back(*it);
            st.erase(it);
        }
    }
    return ans;
}

vector<int> maximalPermutation()
{
    st.clear();
    for(int i = 1; i <= n; i++)
        st.insert(i);
    vector<int> ans;
    ans.push_back(a[0]);
    st.erase(a[0]);
    for (int i = 1; i < n; i++)
    {
        if (a[i] != a[i - 1]) 
        {
            st.erase(a[i]);
            ans.push_back(a[i]);
        }
        else 
        {
            auto it = --st.lower_bound(ans.back());
            ans.push_back(*it);
            st.erase(it);
        }
    }
    return ans;
}

     		 		 		  	 	  	   				 		