#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;

#define nmax 500005

int n,l,v[nmax],batog[nmax],c;

void citire()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&v[i]);
}

void solve()
{
    l=sqrt(n);
    while(c*l<n)
    {
        for(int i=c*l+1;i<=(c+1)*l&&i<=n;++i)
        if(batog[c+1]<v[i]) batog[c+1]=v[i];
        c++;
    }
    for(int k=1;k<=c;++k)
    printf("%d ",batog[k]);printf("\n");
    int x=0,m,a;
    for(int i=1;i<=n;++i)
    {
        m=0;
        for(int j=1;j<=c;++j)
            if(batog[j]>m)
            {
                m=batog[j];
                a=j;
            }
        for(int j=(a-1)*l+1;j<=a*l&&j<=n-x;++j)
        {
            if (v[j]==m)
            {
                swap(v[j],v[n-x]);
                x++;
                break;
            }
        }
        //printf("%d\n",a);
        batog[a]=0;
        for(int j=(a-1)*l+1;j<=a*l&&j<=n-x;++j)
        {
            if(batog[a]<v[j]) batog[a]=v[j];
        }
        //for(int k=1;k<=n;++k) printf("%d ",v[k]); printf("\n");
        if(n-x<=(c-1)*l)
        c--;
        else
        {
            batog[c]=0;
            for(int j=(c)*l+1;j<n-x;++j)
                if(batog[c-1]<v[j]) batog[c-1]=v[j];
    //for(int k=1;k<=c;++k) printf("%d ",batog[k]);printf("\n");
        }
    }
    for(int i=1;i<=n;++i) printf("%d ",v[i]);
}

int main()
{
    freopen("algsort.in","r",stdin);
    freopen("algsort.out","w",stdout);
    citire();
    solve();
}