#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_NUM_OF_QUEUE 2000000
#define PARENT(i) ((i)>>1)
#define LEFT(i)   ((i)<<1)
#define RIGHT(i)  (((i)<<1)+1)

static int queueS[MAX_NUM_OF_QUEUE];

/**
 * @brief queueSの配列を並び替える
 *
 *        queueS[sortIndex]の値を親とし子の値と比較をして
 *        子の方が大きかったら親と子の値を入れ替える。
 *
 * @param [in]  sortIndex 入れ替え対象となる親のindex
 * @param [in]  insertNum queueS配列に入っている値の数
 *
 * @return   -1     入れ替えは発生しなかった
 *           -1以外 入れ替えた先のindexの値
 *
 */
int sortQueue(int sortIndex, int insertNum)
{
    int leftIndex, rightIndex, maxIndex, temp;
    
    /* 子のindexを計算 */
    leftIndex = LEFT(sortIndex);
    rightIndex = RIGHT(sortIndex);
    
    /* indexが小さい方の子と親の値を比較 */
    if((leftIndex < insertNum) && (queueS[leftIndex] > queueS[sortIndex])){
        maxIndex = leftIndex;
    }else{
        maxIndex = sortIndex;
    }
    /* 上で値が大きかった方のindexとindexが大きい方の子の値を比較 */
    if((rightIndex < insertNum) && (queueS[rightIndex] > queueS[maxIndex])){
        maxIndex = rightIndex;
    }
    /* maxが引数でもらったindexではなかった場合は入れ替え */
    if(maxIndex != sortIndex){
        temp = queueS[sortIndex];
        queueS[sortIndex] = queueS[maxIndex];
        queueS[maxIndex] = temp;
    }else{
        return -1;
    }
    
    return maxIndex;
}

/**
 * @brief insert処理を行う関数
 *
 *        queueS配列にnumberを追加し並び替えをする。
 *
 * @param [in]  number    queueS配列に追加する値
 * @param [in]  insertNum queueS配列に入っている値の数
 *
 */
void insert(int number, int insertNum)
{
    int i, temp;
    
    /* 有効な値の次のindexに値を追加 */
    i = insertNum;
    queueS[i] = number;
    
    /* 追加した値と親のindexにあたる値を比較
       追加した値が大きかったら値を入れ替える、を繰り返す */
    while((i > 0) && (queueS[PARENT(i)] < queueS[i])){
        temp = queueS[i];
        queueS[i] = queueS[PARENT(i)];
        queueS[PARENT(i)] = temp;
        i = PARENT(i);
    }
}

/**
 * @brief extract処理を行う関数
 *
 *        queueS配列から最大の値を取り出し配列の並び替えをする。
 *
 * @param [in]  insertNum queueS配列に入っている値の数
 *
 * @return      0以上  queueS配列最大の値
 *              -1     エラー(queueS配列が空だった)
 *
 */
int extract(int insertNum)
{
    int sortIndex =0;
    int returnValue = queueS[0]; /* 最大の値はqueueS[0]の値 */
    
    /* queueS配列が空だったらエラー */
    if(insertNum == 0){
        return -1;
    }
    
    /* 有効領域の最後の値を空いたqueueS[0]に持ってきて並び替えを行う */
    queueS[0] = queueS[insertNum-1];
    do{
        sortIndex = sortQueue(sortIndex, insertNum);
    }while(sortIndex != -1);
    
    return returnValue;
}

int main()
{
    int insertNum = 0;
    int orderNum = 0;
    int extractValue;
    
    char order[10];
    char value[10];
    
    /* 配列初期化 */
    order[0] = '\0';
    value[0] = '\0';
    
    while(scanf("%s",order)){
        orderNum++;
        if(!strcmp(order, "insert")){
            scanf("%s",value);
            if(atoi(value) > 2000000000){
                printf("insert number is over 2,000,000,000!!\n");
                return -1;
            }
            /* insert処理を行う */
            insert(atoi(value), insertNum);
            insertNum++;
        }else if(!strcmp(order, "extract")){
            /* extract処理を行う */
            extractValue = extract(insertNum);
            if(extractValue != -1){
                printf("%d\n", extractValue);
            }else{
                printf("queue is empty!!\n");
                return -1;
            }
            insertNum--;
        }else if(!strcmp(order, "end")){
            /* endで処理は終了 */
            break;
        }else{
            printf("Invalid order!!\n");
            return -1;
        }
        if(orderNum == 2000010){
            printf("Order Num is over 2,000,000\n");
            return -1;
        }
    }
    return 0;
}

