import java.io.*;
import java.util.NoSuchElementException;

interface PWSchlange
{   void einfügen(Comparable x);
    Comparable entferneMin() throws java.util.NoSuchElementException;
    boolean istleer();
}

class Halde implements PWSchlange
{ 
    int n=0;        // Länge der Halde
    Comparable [] a;  // Halde ist auf a[1] .. a[n] gespeichert.

Halde(int maxLänge) // maxLänge = maximale Länge der Halde
    {	a = new Comparable [maxLänge+1]; }
    
public void einfügen(Comparable x)
{   if (n>=a.length-1) throw new RuntimeException("Feldüberlauf");
    a[++n] = x;
    zuklein(n);
}  

public Comparable entferneMin() throws NoSuchElementException
{   if (n<=0) throw new NoSuchElementException();
    Comparable x = a[1];
    n--;
    if (n>0) {
        a[1] = a[n+1];
        zugroß(1);
    }
    return x;
}
public boolean istleer() {return n==0;}
   
void zuklein(int i) // a[i] ist möglicherweise kleiner als sein Vorgänger.
{   if (i==1) return;
    int Vorgänger = i/2;
    if (a[i].compareTo(a[Vorgänger])<0) {
        vertausche(i,Vorgänger);
        zuklein(Vorgänger);
    }
}

void zugroß(int i) // a[i] ist möglicherweise größer als seine Nachfolger.
{   int kleinsterNachfolger;
    if (2*i+1 <= n) {
        if (a[2*i].compareTo(a[2*i+1])<0) kleinsterNachfolger = 2*i;
        else                              kleinsterNachfolger = 2*i+1;
    }
    else if (2*i <= n) kleinsterNachfolger = 2*i;
    else return;
    if (a[i].compareTo(a[kleinsterNachfolger]) >0) {
        vertausche(i, kleinsterNachfolger);
        zugroß(kleinsterNachfolger);
    }
}

void vertausche(int i, int j)
{ Comparable x=a[i]; a[i]=a[j]; a[j]=x; }

}