#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define b back
#define cout(x) cout << x << endl
#define lb long double
#define soa(arr, n) sort(arr,arr+n)
#define inputVector(v, n) for(int i = 0; i < n; i++) cin >> v[i]
#define vv(n) vector<ll> v(n)
#define sov(v) sort(v.begin(), v.end())
#define rev(v) reverse(v.begin(), v.end())
#define pl pair<ll, ll>
#define all(a)    a.begin(), a.end()
#define vpp vector<pair<ll, ll>>
#define fastIo ios_base::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
typedef long long int  ll;
ll P = 1e9 + 7;

vector<ll> filter(vector<ll> &v) {
    vector<ll> f = {INT_MIN};
    for(auto it: v) {
        if(it != f.back()) f.pb(it);
    }
    f.pb(INT_MIN);
    return f;
}

bool sign(ll val) {
    return val > 0;
}

vector<ll> find_peeks_and_palleys(vector<ll> & v) {
    ll i = 1;
    vector<ll> vv = {v[0]};
    
    while(i < v.size() - 1) {
        if(i == 1) {
            vv.push_back(v[1]);
        }
        if(i + 1  >= v.size() - 1) break;
        ll diff = v[i + 1] - v[i];
        i ++;
        while(i < v.size() - 1 && sign(diff) == sign(v[i] - v[i - 1])) {
            i ++;
        }
        i --;
        vv.push_back(v[i]);
    }
    vv.pb(v.back());
    return vv;
}

// wrong code practice of mutation but in cp can be ignored.
void populate_max(vector<ll> &v) {
    ll i = v.size() - 1;
    ll prev = v.back();
    while(i >= 0) {
        prev = max(prev, v[i]);
        v[i] = prev;
        if(v[i] == INT_MIN) v[i] = -1;
        i --;
    }
}

void populate_min(vector<ll> &v) {
    ll i = v.size() - 1;
    ll prev = v.back();
    while(i >= 0) {
        prev = min(prev, v[i]);
        v[i] = prev;
        if(v[i] == INT_MAX) v[i] = -1;
        i --;
    }
}
void print_vector(vector<ll> &v) {
    for(auto it: v) {
        cout << it << " ";
    }
    cout << endl;
}
void solve() {
    ll n;
    cin >> n;
    vv(n);
    for(ll i = 0; i < n; i ++) {
        cin >> v[i];
    }
    v = filter(v);
    v = find_peeks_and_palleys(v);
    v.erase(v.begin());
    v.pop_back();
    map<ll, ll> pref_sum;
    ll i = 0;
    
    while(i < v.size() - 1) {
        if(v[i] - v[i + 1] > 1) {
            pref_sum[v[i]]  -= 1;
            pref_sum[v[i + 1] + 1] +=1;
        }
        else if(v[i + 1] - v[i] > 1) {
            pref_sum[v[i + 1]] -= 1;
            pref_sum[v[i] + 1] += 1;
        }
        i ++;
    }
    ll sum = 0;
    vector<ll> ans_min(n - 1, INT_MAX), ans_max(n - 1, INT_MIN);
    
    for(auto it: pref_sum) {
        if(sum >= 1) {
            ans_min[sum - 1] = min(ans_min[sum - 1], it.first - 1);
            ans_max[sum - 1] = max(ans_max[sum - 1], it.first - 1);
        }
        sum += it.second;
        if(sum >= 1) {
            ans_min[sum - 1] = min(ans_min[sum - 1], it.first);
            ans_max[sum - 1] = max(ans_max[sum - 1], it.first);
        }
    }
    
    populate_min(ans_min);
    populate_max(ans_max);
    
    print_vector(ans_min);
    print_vector(ans_max);
}

int main() {
    ll t=1,i=2;
    fastIo;
    cin >> t;
    while(t--) {
       // cout << "Case #" << i << ": ";
        solve();
        i++;
    }
    return 0;
}