E. Restoring the Permutation

E. Restoring the Permutation

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

A permutation is a sequence of nn integers from 11 to nn, in which all numbers occur exactly once. For example, [1][1], [3,5,2,1,4][3,5,2,1,4], [1,3,2][1,3,2] are permutations, and [2,3,2][2,3,2], [4,3,1][4,3,1], [0][0] are not.

Polycarp was presented with a permutation pp of numbers from 11 to nn. However, when Polycarp came home, he noticed that in his pocket, the permutation pp had turned into an array qq according to the following rule:

• qi=max(p1,p2,…,pi)qi=max(p1,p2,…,pi).

Now Polycarp wondered what lexicographically minimal and lexicographically maximal permutations could be presented to him.

An array aa of length nn is lexicographically smaller than an array bb of length nn if there is an index ii (1≤i≤n1≤i≤n) such that the first i−1i−1 elements of arrays aa and bb are the same, and the ii-th element of the array aa is less than the ii-th element of the array bb. For example, the array a=[1,3,2,3]a=[1,3,2,3] is lexicographically smaller than the array b=[1,3,4,2]b=[1,3,4,2].

For example, if n=7n=7 and p=[3,2,4,1,7,5,6]p=[3,2,4,1,7,5,6], then q=[3,3,4,4,7,7,7]q=[3,3,4,4,7,7,7] and the following permutations could have been as pp initially:

• [3,1,4,2,7,5,6][3,1,4,2,7,5,6] (lexicographically minimal permutation);
• [3,1,4,2,7,6,5][3,1,4,2,7,6,5];
• [3,2,4,1,7,5,6][3,2,4,1,7,5,6];
• [3,2,4,1,7,6,5][3,2,4,1,7,6,5] (lexicographically maximum permutation).

For a given array qq, find the lexicographically minimal and lexicographically maximal permutations that could have been originally presented to Polycarp.

Input

The first line contains one integer tt (1≤t≤1041≤t≤104). Then tt test cases follow.

The first line of each test case contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105).

The second line of each test case contains nn integers q1,q2,…,qnq1,q2,…,qn (1≤qi≤n1≤qi≤n).

It is guaranteed that the array qq was obtained by applying the rule from the statement to some permutation pp.

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105.

Output

For each test case, output two lines:

• on the first line output nn integers — lexicographically minimal permutation that could have been originally presented to Polycarp;
• on the second line print nn integers — lexicographically maximal permutation that could have been originally presented to Polycarp;

Example

input

Copy

4
7
3 3 4 4 7 7 7
4
1 2 3 4
7
3 4 5 5 5 7 7
1
1

output

Copy

3 1 4 2 7 5 6 
3 2 4 1 7 6 5 
1 2 3 4 
1 2 3 4 
3 4 5 1 2 7 6 
3 4 5 2 1 7 6 
1 
1 

=========================================================================

仅靠循环的话加上一些优化能过9个点，第10个卡住，字典序最小的是容易做的，on即可，而字典序最大的容易找重复，应该用优先队列，每当遇见一个确定位置，就加入上一个确定位置的数字到该确定位置数字之间的数字。每次取最大值即可，也是on，这样就不会超时了

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
 
typedef long long int  ll;
 
int a[200000+10];
 
bool book1[200000+10];
bool book[200000+10];
int ans1[200000+10];
int ans2[200000+10];
priority_queue<int>q;
vector<int>v;
int main()
{
 
 
    int t;
 
    cin>>t;
 
    while(t--)
    {
        int n;
 
        cin>>n;
        for(int i=1; i<=n; i++)
        {
            ans1[i]=0;
            ans2[i]=0;
            book1[i]=0;
            book[i]=0;
        }
        v.clear();
 
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a[i]);
 
            if(a[i]!=a[i-1])
            {
                book1[a[i]]=1;
                book[i]=1;
                ans1[i]=a[i];
                ans2[i]=a[i];
                v.push_back(a[i]);
            }
        }
 
        int pre=a[1],last=1,now=-1;
 
        while(!q.empty())
            q.pop();
 
        for(int i=1; i<=n; i++)
        {
            if(book[i])
            {
                pre=a[i];
                now++;
                int bb;
                if(now==0)
                    bb=1;
                else
                    bb=v[now-1]+1;
                for(int j=bb; j
                {
                    q.push(j);
                }
            }
            else
            {
                ans2[i]=q.top();
                q.pop();
                for(int j=last; j<=pre; j++)
                {
                    if(!book1[j])
                    {
                        ans1[i]=j;
                        book1[j]=1;
                        last=j;
                        break;
                    }
                }
            }
        }
 
 
        for(int i=1; i<=n; i++)
        {
            cout<" ";
        }
        cout<
        for(int i=1; i<=n; i++)
        {
            cout<" ";
        }
        cout<
    }
 
 
 
    return 0;
}