//
//  main.cpp
//  heap-sort
//
//  Created by Catalina Brinza on 11/26/13.
//  Copyright (c) 2013 Catalina Brinza. All rights reserved.
//

#include <fstream>
using namespace std;
ifstream f("algsort.in");
ofstream g("algsort.out");



int main()
{int n,i,x,y,k, a[500000],j,aux;
    f>>n>>x; a[1]=x;k=1;
    for (i=2;i<=n;++i)
    {
        f>>y;
        a[i]=y;
        int in=i;
        while (a[in]<a[in/2])
        {
            a[i]=a[i/2];
            a[i/2]=y;
            in=in/2;
        }
    }
    for (i=1;i<=n;++i) g<<a[i]<<' ';
         g<<"\n";
    int m=n;
    for (i=1;i<=m;++i)
    {
        g<<a[1]<<' ';

        a[1]=a[n];
       
        n--;
 
        j=1;
        bool ok=false;
        while (!ok)
        {
    if (a[j]>a[j*2] && j*2<=n)
    {
        if ((a[j*2+1]<a[j*2]) && (j*2+1<=n))
        {
            aux=a[j*2+1];
            a[j*2+1]=a[j];
            a[j]=aux;
            j=j*2+1;
            if (j==n) break;
        }
        else
        {
            aux=a[j];
            a[j]=a[j*2];
            a[j*2]=aux;
            j=2*j;
            if (j==n) break;
        }
    }
    else if (a[j*2+1]<a[j] && j*2+1<=n)
            {
                aux=a[j*2+1];
                a[j*2+1]=a[j];
                a[j]=aux;
                j=j*2+1;
                if (j==n) break;
            }
            else break;
    
        }
    }

    return 0;
}