#include <bits/stdc++.h>
using namespace std;

#define cin fin
#define cout fout
#define sp << " " <<
#define nl << "\n"

ifstream fin("prob5.in");
ofstream fout("prob.out");

int n, i, j, h[100], k, a;

void insert(int a) {
    n++;
    k++;
    h[k] = a;
}

void aranjeaza(int nn) {
    int x;
    x = h[nn];
    while (nn > 1 && x > h[nn / 2]) {
        h[nn] = h[nn / 2];
        nn = nn / 2;
    }
    h[nn] = x;
}

void coboara(int n) {
    int fiu = -1;
    while (fiu != 0) {
        if (2 * n <= k)
            fiu = 2 * n;
        if (2 * n + 1 <= k && h[2 * n + 1] > h[fiu])
            fiu = 2 * n + 1;


        if (h[fiu] <= h[n])
            fiu = 0;
        if (fiu) {
            swap(h[n], h[fiu]);
            n = fiu;
        }
    }
}


void sterg() {
    if (k < 1) return;
    cout << h[1] << " ";
    h[1] = h[k];
    k--;
    n--;
    coboara(1);
}

void cobor(int a[], int n, int i) {
    int rad = i;
    int st = 2 * i + 1;
    int dr = 2 * i + 2;
    if (st < n && a[st] < a[rad])
        rad = st;
    if (dr < n && a[dr] < a[rad])
        rad = dr;

    if (rad != i) {
        swap(a[i], a[rad]);
        cobor(a, n, rad);
    }
}

void heapsort(int a[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        cobor(a, n, i);

    for (int i = n - 1; i >= 0; i--) {
        swap(a[0], a[i]);
        cobor(a, i, 0);
    }
}

int main() {
    int t;
    k = 0;
    while (cin >> t) {
        insert(t);
        aranjeaza(k);
    }

    cout << "Avem max-heapul: " << endl;
    for (i = 1; i <= k; i++)
        cout << h[i] << " ";
    cout nl nl;


    cout << "Max1: " << h[1] << " " nl;
    sterg();
    cout << "Max2: " << h[1] << " " nl;
    sterg();
    cout << "Max2: " << h[1] << " " nl;
    sterg();

    if (k == 0) {
        cout << "Heapul este gol!" nl;
    } else {

        cout << "Avem max-heapul modificat: " << endl;
        for (i = 1; i <= k; i++)
            cout << h[i] << " ";
        cout nl nl;

        heapsort(h, n+1);

        cout << "Heapul sortat descresc:\n";
        for (i = 1; i <= k; i++)
            cout << h[i] << " ";
        cout << endl;
    }



    return 0;
}