#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

void heap_help(int*,int, int);

void heap_sort(int *a, int n)
{   for(int i=n/2-1; i >= 0; i--) heap_help(a, i, n);
    for(int i=n-1; i>0; i--)
    {   swap(a[0], a[i]);
        heap_help(a, 0, i);
    }
}

void heap_help(int* a, int hole, int n) {
    int  val =a[hole];
    int i = 2*hole+1;
    while (i < n) {
        if ( i < n-1 && a[i] < a[i+1]) i++;
        if(val<a[i]) {
            a[hole] = a[i];
            hole = i;
            i = 2 * i + 1;}
        else i = n;
        }
    a[hole] = val;
}

int main()
{
    int n;
    cin>>n;
    int* a = new int[n];

    for(int i=0; i<n; i++)
       a[i] = rand()%100;
    for(int i=0; i<n; i++)
        cout<<a[i]<<' '; cout<<endl;

    heap_sort(a,n);

    for(int i=0; i<n; i++)
        cout<<a[i]<<' ';

}