#include<iostream>
#include<fstream>

using namespace std;
fstream in("algsort.in",ios::in);
fstream out("algsort.out",ios::out);

void quiq(int*,int,int);
int part(int*,int,int);

int main()
{
    int a[500000],n,i;
    in>>n;
    for(i=0;i<n;i++)
        in>>a[i];
    quiq(a,0,n-1);
    for(i=0;i<n;i++)
        out<<a[i]<<" ";
    out<<"\n";

    for(i=0;i<n;i++)
        cout<<a[i]<<" ";
    out<<"\n";

    in.close();
    out.close();
    return 0;
}

void quiq(int a[],int down,int up)
{
    if(down<up)
    {
        int mid;
        mid=part(a,down,up);
        quiq(a,down,mid-1);
        quiq(a,mid+1,up);
    }
}

int part(int a[],int down,int up)
{
    int p,ip,j,x,i;
    ip=(up+down)/2;
    p=a[ip];
    a[ip]=a[up];
    a[up]=p;
    j=down;
    for(i=down;i<up;i++)
        if(a[i]<p)
        {
            x=a[i];
            a[i]=a[j];
            a[j]=x;
            j++;
        }
    x=a[j];
    a[j]=a[up];
    a[up]=x;
    return j;
}