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

typedef struct node *link;
typedef int Item;
struct node {
    Item item;
    link next;
};
static link head, tail;

void Queueinit (int maxN) { head = NULL; }
int Queueenpty (void) { return head == NULL; }
Item Queueget (void) {
    Item item = head->item;
    link t = head->next;
    free(head);
    head = t;
    return item;
}
Item Queueget_i (Item i) {
    link t = head, pre = NULL;
    while (t != NULL) {
        if (t->item == i) {
            if (pre != NULL) {
                pre->next = t->next;
                if (t == tail) tail = pre;
            }
            if (t == head) head = t->next;
            free(t);
            return i;
        }
        pre = t;
        t = t->next;
    }
    return -1;
}
link NEW(Item item, link next) {
    link x = malloc(sizeof * x);
    x->item = item;
    x->next = next;
    return x;
}
void Queueput (Item item) {
    if (head == NULL) {
        head = (tail = NEW(item, head));
        return;
    }
    tail->next = NEW(item, tail->next);
    tail = tail->next;
}
Item QueueMax (void) {
    link t = head;
    Item max = -1;
    while (t != NULL) {
        if (max < t->item) max = t->item;
        t = t->next;
    }
    return max;
}

int main(void) {
    Item data;
    char command[12];
    Queueinit(1000);
    while (1) {
        scanf("%s", command);
        if (!strcmp(command, "insert")) {
            scanf("%d", &data);
            Queueput(data);
        } else if (!strcmp(command, "extract")) {
            printf("%d\n", Queueget_i(QueueMax()));
        } else if (!strcmp(command, "end")) {
            break;
        } else printf("Invalid Command.\n");
    }
    return 0;
}
