#include <bits/stdc++.h>
#define cin fin
#define cout fout
#define NMAX 10000
using namespace std;
ifstream cin ("heap.in");
ofstream cout ("heap.out");
int n,nr,i,el;
int H[NMAX];
void inserare(int H[], int&n, int x)
{
    int fiu, tata;
    fiu=n+1;
    tata=fiu/2;
    while(tata && H[tata]>x)
    {
        H[fiu]=H[tata];
        fiu=tata;
        tata=fiu/2;
    }
    H[fiu]=x;
    n++;
}
void creare_inserare(int H[], int &n)
{
    n=0;
    cin>>nr;
    for(i=0;i<nr;i++)
    {
        cin>>el;
        inserare(H,n,el);
    }
}
void combinare(int H[],int n,int poz)
{
    ///combin H[poz] cu heapurile corecte cu radacinile de pozitie 2*poz 2*poz+1
    int x=H[poz],fiu ,tata;
    tata=poz;
    fiu=tata*2;
    while(fiu<=n)
    {
        if(fiu+1<=n && H[fiu+1]<H[fiu])
            fiu++;
        if(H[fiu]>=x)
            break;
        H[tata]=H[fiu];
        tata=fiu;
        fiu=2*tata;
    }
    H[tata]=x;
}
void creare_combinare(int H[],int n)
{
    for(int i=n/2;i>0;i--)
        combinare(H,n,i);
}
void citire(int H[],int &n)
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>H[i];
}
void afisare(int H[], int n)
{
    for(i=1;i<=n;i++)
        cout<<H[i]<<" ";
}
int Extragemin(int H[],int &n)
{
    int minim=H[1];
    H[1]=H[n];
    n--;
    combinare(H,n,1);
    return minim;
}
int main()
{
    /*creare_inserare(H,n);*/
    citire(H,n);
    creare_combinare(H,n);
    afisare(H,n);
    cout<<'\n'<<Extragemin(H,n)<<'\n';
    afisare(H,n);
    return 0;
}