#include <iostream>
#include <stdexcept>
#include <limits>

typedef int TChave;

class Torneio {
    friend std::ostream& operator << (std::ostream& saida, const Torneio& h);
    public:
        // Construtor sem valores
        Torneio(int tam);
        // Construtor com valores
        Torneio(TChave vet[], int tam);
        ~Torneio();
        void Inserir(TChave chave);
        // Retorna o vencedor do torneio (maior) sem removê-lo.
        TChave Raiz();
        TChave Retirar();
        bool Vazio();
    protected:
        // Atualiza uma posição, com base em seus dois filhos.
        void Atualizar(int i);//Corrige Descendo
        // Atualiza um toneiro subindo a partir da posicao dada. Util para inserção.
        void ArrumarSubindo(int i);//Corrige Subindo
        // Atualiza todos os não intermediários do torneio.
        void ArrumarTudo();//heapify
        // Calcula o espaço necessário e inicializa atributos. Usado nos contrutores.
        void CalcularEspacoDeArmazenamento(int tam);
        // Calcula a posição do filho direito de um noh.
        inline int Direito(int i);
        // Calcula a posição do filho esquerdo de um noh.
        inline int Esquerdo(int i);
        // Calcula a posição do pai de um noh.
        inline int Pai(int i);

        TChave* mVetChaves; // espaço de armazenamento
        int mCapacidade; // quantidade máxima de nohs
        int mTamanho; // quantidade de noh utilizados
        int mNroTorneios; // quantidade de nohs intermediários
        TChave mMenor; // valor especial que indica ausência de valor
};

using namespace std;

Torneio::Torneio(int tam) {
    CalcularEspacoDeArmazenamento(tam);
    mMenor = numeric_limits<TChave>::min();
    mTamanho = mNroTorneios;
    for (int i = 0; i < mCapacidade; ++i)
        mVetChaves[i] = mMenor;
}

Torneio::Torneio(TChave vet[], int tam) {
    CalcularEspacoDeArmazenamento(tam);
    mMenor = numeric_limits<TChave>::min();
    mTamanho = mNroTorneios + tam;
    int i = 0;
    // copiar dados do vetor para o torneio
    for (; i < tam; ++i) {
        mVetChaves[mNroTorneios+i] = vet[i];
    }
    // posicoes extras ganham a menor chave para completar nós intermediarios
    i += mNroTorneios;
    while (i < mCapacidade)
        mVetChaves[i++] = mMenor;
    ArrumarTudo();
}

Torneio::~Torneio() {
    delete[] mVetChaves;
}

void Torneio::Atualizar(int i) {//-------------------------------certo?
    // completar aqui
    int esq = Esquerdo(i);
    int dir = Direito(i);
    int pos_maior = i;//começa supondo que "i" é a posição do maior
    if(esq < mTamanho && mVetChaves[esq] > mVetChaves[i]){//Testa se possui filho esquerdo. Se sim, testa se o filho esquerdo é maior que o valor atual
        pos_maior = esq;//a posição do maior passa a ser a do filho esquerdo
    }
    if(dir < mTamanho && mVetChaves[dir] > mVetChaves[pos_maior]){//Testa se possui filho direito. Se sim, testa se o filho direito é maior que o maior
        pos_maior = dir;//a posição do maior passa a ser a do filho direito
    }
    if(pos_maior != i){//se a posição do maior não é a posição do atual
        mVetChaves[i] = mVetChaves[pos_maior];//o atual recebe o maior
        Atualizar(pos_maior);//chama "Corrige Descendo" na posição do maior
    }
}

void Torneio::ArrumarSubindo(int i) {//---------------------------certo?
    // completar aqui
    int p = Pai(i);
    if(p >= 0 && mVetChaves[i] > mVetChaves[p]){//se possui pai, e o valor dele é maior que o do pai
        mVetChaves[p] = mVetChaves[i];//o pai recebe o valor dele
        ArrumarSubindo(p);//chama "Corrige Subindo" na posição do pai
    }
}

void Torneio::ArrumarTudo() {//------------------------------------certo?
    // completar aqui
    for (int i = (mTamanho-1)/2; i > 0 ; --i)
    {
        Atualizar(i);
    }
}

void Torneio::CalcularEspacoDeArmazenamento(int tam) {
    mNroTorneios = 1;
    while (mNroTorneios < tam)
        mNroTorneios *= 2;
    mCapacidade = 2 * mNroTorneios - 1;
    mNroTorneios -= 1;
    mVetChaves = new TChave[mCapacidade];
}

int Torneio::Pai(int i) {
    return (i-1)/2;
}

int Torneio::Esquerdo(int i) {
    return 2*i+1;
}

int Torneio::Direito(int i) {
    return 2*i+2;
}

TChave Torneio::Raiz() {//--------------------------------------errado?
    if (mTamanho == mNroTorneios)
        throw runtime_error("Impossível acessar raiz de torneio vazio.");
    // completar aqui
    return mVetChaves[0];
}

TChave Torneio::Retirar() {//----------------------------------------certo?
    if (mTamanho == mNroTorneios)
        throw runtime_error("Impossível retirar de torneio vazio.");
    // completar aqui
    TChave aux = Raiz();//armazena valor da raiz



    //-------------------------------------------------------------------------------------------INCOMPLETO

    //~ swap(mVetChaves[0]. mVetChaves[mTamanho-1]);//troca a raiz com o ultimo elemento
    int i = 0;//começando pela raiz
    int esq = Esquerdo(0);//para testar se entra no while
    int dir;
    mVetChaves[0] = mMenor;//"remove" a raiz
    //esse while transforma todos os resquícios do valor da raiz em mMenor
    while(esq < mCapacidade){//enquanto o ultimo testado possui algum filho (se não tiver filho esquerdo, não tem direito)
        esq = Esquerdo(i);
        dir = Direito(i);
        if(aux == mVetChaves[esq]){
            i = esq;
        }
        if(dir < mCapacidade && aux == mVetChaves[dir]){
            i = dir;
        }
        mVetChaves[i] = mMenor;//"remove" o valor que está sendo retirado
    }
    Atualizar(0);//atualiza a raiz
    return aux;//efetua ação desejada com o valor armazenado
}

bool Torneio::Vazio() {
    return mTamanho == mNroTorneios;
}

void Torneio::Inserir(TChave chave) {//------------------------------certo?
    if (mTamanho == mCapacidade)
        throw runtime_error("Impossível inserir em torneio cheio.");
    // completar aqui
    mVetChaves[mTamanho] = chave;
    ArrumarSubindo(mTamanho);
    mTamanho++;
}

std::ostream& operator << (std::ostream& saida, const Torneio& t) {
    // Operador de escrita pode ser util para depurar o torneio.
    saida << '[';
    TChave chave;
    for (int i=0; i < t.mNroTorneios; ++i) {
        chave = t.mVetChaves[i];
        if (chave == t.mMenor)
            saida << "## ";
        else
            saida << chave << ' ';
    }
    saida << '|';
    int pos = t.mNroTorneios;
    int limite = t.mTamanho;
    while (pos < limite) {
        chave = t.mVetChaves[pos];
        if (chave == t.mMenor) {
            saida << " ##";
            ++limite;
        }
        else
            saida << ' ' << chave;
        ++pos;
    }
    saida << ']';
    return saida;
}

int main() {
    int capacidade; // nro de valores que quero guardar no torneio
    cin >> capacidade;
    Torneio torneio(capacidade);
    TChave chave;
    char operacao;
    do {
        cin >> operacao;
        switch (operacao) {
            case 'i': // Inserir
                try {
                    cin >> chave;
                    torneio.Inserir(chave);
                }
                catch (runtime_error& e) {
                    cerr << e.what() << endl;
                }
                break;
            case 'r': // Remover
                try {
                    cout << torneio.Retirar() << endl;
                }
                catch (runtime_error& e) {
                    cerr << e.what() << endl;
                }
                break;
            case 'e': // Escrever
                cout << torneio << endl;
        }
    } while (operacao != 'f'); // Finalizar execução
    return 0;
}