#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <nmmintrin.h>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <queue>
#include <cmath>
#include <climits>
#include <bitset>
#include <random>
#include <ctime>
#include <chrono>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <sstream>
using namespace std;

void FillInc(int n, int* a);
void FillDec(int n, int* a);
void FillRand(int n, int* a);
void swap(int* xp, int* yp);
void PrintMas(int n, int* a);
void heapify(int* a, int l, int r, int& c, int& m);
void HeapSort(int n, int* a, int& T);
void PrintTabl();

int main()
{
    int T = 0;
    int n;
    int* a;
    cin >> n;
    a = new int[n];
    FillRand(n, a);
    PrintMas(n, a);
    cout << endl;
    HeapSort(n, a, T);
    PrintMas(n, a);
    PrintTabl();
}

void heapify(int* a, int l, int r, int& c, int& m)
{
    int x = a[l], j;
    int i = l;
    ++m;
    while (i < r/2)
    {
        j = 2 * i;
        ++c;
        if ((j < r) && (a[j + 1] <= a[j]))
            j++;
        ++c;
        if (x <= a[j])
        {
            break;
        }
        ++m;
        a[i] = a[j];
        i = j;
    }
    ++m;
    a[i] = x;
}

void HeapSort(int n, int* a, int& T)
{
    int l = n / 2, c = 0, m = 0;
    while (l > 0)
    {
        heapify(a, l, n, c, m);
        --l;
    }
    int r = n ;
    while (r > 1)
    {
        m += 3;
        swap(a[1], a[r]);
        r--;
        heapify(a, 1, r, c, m);
    }
    T = c + m;

}

void FillInc(int n, int* a)
{
    for (int i = 1; i <= n; ++i)
    {
        a[i] = i;
    }
}

void FillDec(int n, int* a)
{
    for (int i = n; i >= 1; i--)
    {
        a[n - i] = i;
    }
}
void FillRand(int n, int* a)
{
    for (int i = 1; i <= n; ++i)
    {
        a[i] = rand() % n;

    }
}
void swap(int* xp, int* yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
void PrintMas(int n, int* a)
{
    for (int i = 1; i < n; ++i)
    {
        cout << a[i] << " ";
    }
}

void PrintTabl()
{
    int n = 1, FR = 0, FD = 0, FI = 0;
    int* a = new int[n];
    cout << endl << "|                 HeapSort               |" << endl;
    cout << "| n |  FillInc  |  FillDec  |  FillRand  |" << endl;

    for (int n = 100; n <= 500; n += 100)
    {
        int T = 0;
        FillRand(n, a);
        HeapSort(n, a, T);
        FR = T;
        FillInc(n, a);
        HeapSort(n, a, T);
        FI = T;
        FillDec(n, a);
        HeapSort(n, a, T);
        FD = T;
        cout << "|" << n << "|" << setw(11) << FI << "|" << setw(11) << FD << "|" << setw(12) << FR << "|" << endl;
    }

    delete[] a;
}