#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

//============================================================================
#define pred(x) ((x)-1)
#define succ(x) ((x)+1)
//============================================================================
#define MAX_QUEUE 0x7fffffff
struct queue{
    long key;
    struct queue *next;
    struct queue *prev;
};
typedef struct queue TQueue;
//============================================================================
TQueue *queuealloc(void)
{
    TQueue *que;

    que=malloc(sizeof(TQueue));
    memset(que, 0, sizeof(TQueue));
    return que;
}
//----------------------------------------------------------------------------
void insertkey(TQueue **S, long k)
{
    TQueue *que,*src;

    que=queuealloc();
    que->key=k;
    if (!*S){
        *S=que;
    }else{
        src=*S;
        src->next->prev=que;
        que->next=src->next;
        que->prev=src;
        src->next=que;
    }
}
//----------------------------------------------------------------------------
void insert(TQueue **S, long k)
{
    TQueue *que;

    if (!*S){
        insertkey(S, k);
    }else{
        que=*S;
        while(k<que->key && que->next)
            que=que->next;
        if (que->key<k){
            insertkey(&que->prev, k);
            if (*S==que){
                *S=que->prev;
                que->prev->next=que;
            }

        }else{
            insertkey(&que->next, k);
        }
    }
}
//----------------------------------------------------------------------------
void deletenode(TQueue *S)
{
    S->prev->next=S->next;
    if (S->next)
        S->next->prev=S->prev;
    free(S);
}
//----------------------------------------------------------------------------
long extractMax(TQueue **S)
{
    long max; TQueue *que;

    que=*S;
    max=(*S)->key;
    *S=(*S)->next;
    if ((*S)->prev)
        (*S)->prev=NULL;
    free(que);
    return max;
}
//----------------------------------------------------------------------------
void input(FILE *file)
{
    long i,n,m; TQueue *queue,*node; char buffer[20];

    queue=NULL;//nodealloc();;
    for (i=0; i<n; i++){
        fgets(buffer, sizeof(buffer)-1, file);
        switch(*buffer){
            case 'i':   sscanf(buffer+7, "%ld", &m);
                        insert(&queue, m);
                    break;
            case 'e':   if (buffer[1]=='x'){
                            m=extractMax(&queue);
                            printf("%ld\n", m);
                            //deletenode(root, node);
                        }else
                            return;
                    break;
        }
    }
}
//============================================================================
#ifndef DESKTOP
int main()
{
    input(stdin);
    return 0;
}
#endif