/* 
 * File:   main.c
 * Author: kundaikwangwari
 *
 * Created on July 16, 2019, 2:19 PM
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define LIM 1500000


int HeapSize;

void swap(int *A, int i, int j){
    
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

void Insert(int *A, int i){
    //printf("am in insert\n");
    while((i > 1) && (A[i/2] < A[i])){
        swap(A,i,i/2);
        i = i/2;
    }
}
void MaxHeapify(int *A, int i){
    //printf("am in maxheapify\n");
    int LF, RL, PN, largest;
    LF = 2*i;
    RL = 2*i + 1;
      // select the node which has the maximum value
      if((LF <= HeapSize) && (A[LF] > A[i]))largest = LF;
      else largest = i;
      if((RL <= HeapSize) && (A[RL] > A[largest]))largest = RL;
    
     if(largest != i){
         // value of children is larger than that of i
         swap (A,i,largest);
         MaxHeapify(A,largest);
     }
}

void HeapExtractMax(int *A){
    //printf("in heapextract\n");
    int topValue;
/*
    if(HeapSize < 1){
        printf("Error, HeapSize underflow. Program terminated...\n");
        return;
    }
*/
    
    topValue = A[1];
    A[1] = A[HeapSize];
    HeapSize--;
    MaxHeapify(A,1);
    printf("%d\n",topValue);
    return;
    
}

int main(int argc, char** argv) {

    
    int sol;
    char cmd[12];
    int A[LIM];
    A[0] = -1;
    for(int i = 1;; i++){
       
        //printf("extracting\n");
        scanf("%s",&cmd);
        

        if(cmd[2]=='d'){
            //printf("end reached");
            break;
        }
        if(cmd[0] == 'i'){
            HeapSize++;
            scanf("%d",&A[HeapSize]);
            Insert(A,HeapSize);
            continue;
        }
        if(cmd[1]=='x'){
            HeapExtractMax(A);
            continue;
        }
               
    }
 return 0;   
}






