#include<stdio.h>
using namespace std;
int p1,aux1,x,i,u,n,aux,h[101];
int heapup()
{
    int p,aux;
    u++;
    h[u]=x;
    p=u;
    while(1)
    {
        if(p==1||h[p/2]>=x) break;
        else
        {
            aux=h[p/2];
            h[p/2]=h[p];
            h[p]=aux;
            p=p/2;
        }
    }
}
int heapdown()
{
    int p1=1,aux2;
    aux2=h[1];
    x=h[u];
    h[1]=h[u];
    h[u]=aux1;
    h[u]=0;
    u--;
    while(1)
    {
        if(h[p1]>=h[p1*2]&&h[p1]>=h[p1*2+1]||p1>=u||h[p1]>h[p1*2]&&p1*2+1>u||p1*2>u) break;
        else
        {
            if(h[p1*2]>h[p1*2+1]&&p1*2<=u)
            {
                aux1=h[p1*2];
                h[p1*2]=x;
                h[p1]=aux1;
                p1=p1*2;
            }
            else
            if(p1*2+1<=u)
            {
                aux1=h[p1*2+1];
                h[p1*2+1]=x;
                h[p1]=aux1;
                p1=p1*2+1;
            }
        }
    }
    h[u+1]=aux2;
}
int heapsort()
{
    int i3;
    for(i3=1;i3<=n-1;i3++)
        heapdown();
}
int main()
{
freopen("algsort.in","r",stdin);
freopen("algsort.out","w",stdout);
scanf("%d",&n);
u=0;
for(i=1;i<=n;i++)
{
    scanf("%d",&x);
    heapup();
}
//for(i=1;i<=n;i++)
  //  printf("%d ",h[i]);
//printf("\n");
heapdown();
for(i=1;i<=n-1;i++)

    printf("%d ",h[i]);
printf("\n");
heapsort();
for(i=1;i<=n;i++)
    printf("%d ",h[i]);
return 0;
}