#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 2000001
int parent(int);
int left(int);
int right(int);
void buildMaxHeap(int*);
void maxHeapify(int*,int);
void swap(int*,int,int);
void printHeap(int*);
void insert(int*,int);
int extract(int*);
int h=0;//size of heap
int main(void)
{
  int arr[N];//array (1-origin)
  char op[10];//operation
  int key;
  for(;;)
    {
      scanf("%s",op);
      if(strcmp(op,"insert")==0)
	{
	  scanf("%d",&key);
	  insert(arr,key);
	}
      if(strcmp(op,"extract")==0) printf("%d\n",extract(arr));
      if(strcmp(op,"print")==0) printHeap(arr);//for debugging
      if(strcmp(op,"end")==0) break;
      
    }
  return 0;
}
int parent(int i)
{
  return i/2;
}
int left(int i)
{
  return 2*i;
}
int right(int i)
{
  return 2*i+1;
}
void buildMaxHeap(int *arr)
{
  int i;//counter
  for(i=h/2;i>=1;i--) maxHeapify(arr,i);
}
void maxHeapify(int *arr,int i)
{
  int l=left(i);
  int r=right(i);
  int largest;
  if(l<=h&&arr[l]>arr[i]) largest=l;
  else largest=i;
  if(r<=h&&arr[r]>arr[largest]) largest=r;
  if(largest!=i)
    {
      swap(arr,i,largest);
      maxHeapify(arr,largest);
    }
}
void swap(int *arr,int x,int y)
{
  int temp;
  temp=arr[x];
  arr[x]=arr[y];
  arr[y]=temp;
}
void printHeap(int *arr)
{
  int i;
  for(i=1;i<=h;i++) printf(" %d",arr[i]);
  printf("\n");
}
void insert(int *arr,int key)
{
  h++;
  arr[h]=key;
  buildMaxHeap(arr);
}
int extract(int *arr)
{
  int ret=arr[1];
  arr[1]=arr[h];
  h--;
  buildMaxHeap(arr);
  return ret;
}
