#include <iostream>
#include <vector>
#include <string>

using namespace std;

#define MAX_OPERATION_NUM 20000000  // 命令の素数
#define MAX_OPERATION_TYPE 4        // 命令種別 + 命令判別用の空文字
#define MAX_INT 2000000000                    //
#define LEFT_CHILD(x)   ((2 * x) + 1) 
#define RIGHT_CHILD(x)  (2 * (x + 1))
#define PARENT(x)       ((x - 1) >> 1)
#define ROOT            0
#define SUCCESS         0
#define ERROR           0xFFFFFFFF

// 命令の種別
string strOperation[MAX_OPERATION_TYPE] =
{
    // 命令の判別の、終点用に空文字を末尾に追加
    "insert","extract","end",""
};

unsigned int Insert(vector<unsigned int> &v, unsigned int ulKey)
{
    // Queueが満たされているなら、エラーを返す
    if(v.size() == MAX_OPERATION_NUM)
    {
        return ERROR;
    }
    
    // 挿入する値が制約を満たさない場合、エラーを返す(unsigned なので0の比較は省略)
    if(ulKey > MAX_INT)
    {
        return ERROR;
    }
    
    // 末尾に追加
    v.push_back(ulKey);
    
    // 末尾の要素を比較対象に設定
    unsigned int ulTarget = v.size() - 1; 
    //cout << v[ROOT] << " " << v[v.size() - 1] << endl;
    // 根に到達するまで比較する
    while(ulTarget != ROOT)
    {
        // 親と比較し、大きければ交換
        unsigned int ulParent = PARENT(ulTarget);
        //cout <<"比較" << v[ulTarget] << " " << v[ulParent] << endl;
        if(v[ulTarget] > v[ulParent])
        {
            swap(v[ulTarget], v[ulParent]);
            //cout << v[ulTarget] << endl;
            // 次回の比較対象を親の要素とする
            ulTarget = ulParent;
        }
        else
        {
            // 交換できないなら終了
            return SUCCESS;
        }
    }
    
    return SUCCESS;
}

unsigned int Extract(vector<unsigned int> &v)
{
    unsigned int ulRslt = SUCCESS;
    //cout << "サイズ" << v.size() - 1 << endl;
    // Queueが空なら、エラーを返す
    if(v.empty())
    {
        return ERROR;
    }
    
    // 先頭と末尾の要素を交換
    ulRslt = v[ROOT];
    //cout << v[ROOT] << " " << v[v.size() - 1] << endl;
    swap(v[ROOT], v[v.size() - 1]);
    // 末尾の要素を削除
    v.pop_back();
    
    // 先頭を比較対象に設定
    unsigned int ulTarget = ROOT;
    
    // 葉に到達するまで比較する
    while(ulTarget < (v.size() - 1))
    {
        unsigned int ulLeft = LEFT_CHILD(ulTarget);
        unsigned int ulRight = RIGHT_CHILD(ulTarget);
        unsigned int ulTmp;
        // 子が範囲外かどうかを確認
        if((ulLeft > (v.size() - 1)) && (ulRight > (v.size() - 1)))
        {
            return ulRslt;
        }
        else
        {
            if(ulRight <= (v.size() - 1))
            {
                if(v[ulRight] > v[ulLeft])
                {
                     ulTmp = ulRight;
                }
                else
                {
                    ulTmp = ulLeft;
                }
            }
            else
            {
                ulTmp = ulLeft;
            }
        }
        
        //cout <<"比較2 " << v[ulTarget] << " " << v[ulTmp] << endl;
        if(v[ulTarget] < v[ulTmp])
        {
            swap(v[ulTarget], v[ulTmp]);
            //cout << v[ulTarget] << endl;
            // 次回の比較対象を交換した要素にする
            ulTarget = ulTmp;
        }
        else
        {
            // 交換できないなら終了
            return ulRslt;
        } 
    }
    
    return ulRslt;
}

int main(void){
    vector<unsigned int> ulvecQueue;
    unsigned int ulOpeIdx;
    unsigned int ulKey;
    string s; 
    unsigned int ulRslt;
    
    ulvecQueue.reserve(MAX_OPERATION_NUM);
    
    
    // 1行を読み込み、取り出せる命令によってヒープを操作する
    while(cin >> s)
    {
        //cout << s << endl;
        // 命令を判別する
        for(ulOpeIdx = 0; ulOpeIdx < MAX_OPERATION_TYPE; ulOpeIdx++)
        {
            // 命令が一致した場所を判定し、インデックスとする
            if(!s.compare(strOperation[ulOpeIdx]))
            {
                break;
            }
        }
        //cout << "idx" << ulOpeIdx << " ";
        
        switch(ulOpeIdx)
        {
            case 0:
                cin >> ulKey;
                //cout << "key" << ulKey << endl;
                ulRslt = Insert(ulvecQueue, ulKey);
                break;
            case 1:
                ulRslt = Extract(ulvecQueue);
                //cout << "出力 " << ulRslt << endl;
                cout << ulRslt << endl;
                break;
            case 2:
                // end なので終了
                //cout << "終了" << endl;
                return 0;
            default:
                // 定義されていない命令以外ならエラー終了
                return -1;
        }
        
        // 戻り値がエラー値なら終了
        if(ulRslt == ERROR)
        {
            return -1;
        }
    }
    
    return 0;
}





Measured memory_bytes: 6836