#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

vector < int > a(500001);

int n;

void read();
void solve();
void build();
void comb(int,int);


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

void read ()
{
   int i;
   scanf("%ld",&n);
   //a.reserve(n+1);
   for (i=1;i<=n;++i)
      scanf("%ld",&a[i]);
}

void solve()
{
   int i;
   build();
   for (i=n;i;--i)
   {
      printf("%ld ",a[1]);
      swap(a[1],a[i]);
      --n;
      comb(1,i-1);
   }
}

void build ()
{
   int x=0,i;
   if (n>1)
   {
      if (n%3==1) x=-1;
      if (n%3==2) x=1;
   }
   for (i=(n+x)/3;i;--i)
      comb(i,n);
}

void comb (int t,int n)
{
   int aux,q,c;
   aux=a[t];
   q=t*3-1;
   c=q;
   while (c<=n)
   {
      if (a[q+1]<a[c]&&q+1<=n) c=q+1;
      if (a[q+2]<a[c]&&q+2<=n) c=q+2;
      if (a[c]<aux)
      {
         a[t]=a[c];
         t=c;
         q=t*3-1;
         c=q;
      }
      else c=n+1;
   }
   a[t]=aux;
}