/* 
 * File:   main.c
 * Author: s1252007
 *
 * Created on July 27, 2018, 12:05 PM
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 5000001

/*
 * 
 */

int H, Heap[MAX];

void maxHeapify(int i);
int extract();
void insert(int key);

int main(int argc, char** argv) {
    int key;
    char command[15];
    while (1)
    {
        scanf("%s", command);
        if (strcmp(command, "extract") == 0) printf("%d\n", extract());
        if (strcmp(command, "insert") == 0)
        {
            scanf("%d", &key);
            insert(key);
        }
        else if (strcmp(command, "end") == 0) break;
    }
    return (EXIT_SUCCESS);
}

void maxHeapify(int i)
{
    int left, right, max, temp;
    left = i*2;
    right = i*2+1;
    
    if (left <= H && Heap[left] > Heap[i]) max = left;
    else max = i;
    if (right <= H && Heap[right] > Heap[max]) max = right;
    
    if (max != i)
    {
        temp = Heap[i];
        Heap[i] = Heap[max];
        Heap[max] = temp;
        maxHeapify(max);
    }
}

int extract()
{
    int max;
    if (H < 1) return -1;
    max = Heap[1];
    Heap[1] = Heap[H--];
    maxHeapify(1);
    return max;
}

void insert(int key)
{
    Heap[++H] = -1;
    int i = H, temp;
    if (key < Heap[i]) return;
    Heap[i] = key;
    while ( i > 1 && Heap[i/2] < Heap[i])
    {
        temp = Heap[i];
        Heap[i] = Heap[i/2];
        Heap[i/2] = temp;
        i = i/2;
    }
}



