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

typedef struct node{
  long key;
  struct node *left;
  struct node *right;
  struct node *p;
  struct node *max;
}Node;

Node *max = NULL;

Node *insert(Node *root, long key) {
  Node *z = (Node*)malloc(sizeof(Node));
  z->key = key;
  z->p = NULL;
  z->left = NULL;
  z->right = NULL;
  z->max = z;
  if(root == NULL) {
    max = z;
    return z;
  }
  if(max->key <= z->key) {
    z->p = max;
    max->right = z;
    max = z;
    return root;
  }
  Node *x,*y;
  int t = 0;
  y = NULL;
  x = root;
  while(x != NULL) {
    y = x;
    if(z->key < x->key) {
      x = x->left;
      t = 1;
    }else {
      if(t != 0 && x->max->key <= z->key) x->max = z;
      x = x->right;
    }
  }
  z->p = y;
  if(z->key < y->key) y->left = z;
  else y->right = z;
  return root;
}

Node *extract(Node *root) {
  printf("%ld\n",max->key);
  Node *x = max,*y = max->p;
  if(x->left == NULL && x->right == NULL) {
    if(y == NULL) {
      max = NULL;
      free(x);
      return NULL;
    }
    y->right = NULL;
    max = y;
    free(x);
    return root;
  }
  else {
    Node *z = x->left;
    if(y == NULL) {
      max = z->max;
      free(x);
      z->p = NULL;
      return z;
    }
    z->p = y;
    y->right = z;
    max = z->max;
    free(x);
    return root; 
  }
}


int main()
{
  long key;
  char command[8];
  Node *root = NULL;
  while (1) {
    scanf("%s",command);
    if(strcmp(command,"insert") == 0) {
      scanf("%ld",&key);
      root = insert(root,key);
    }
    if(strcmp(command,"extract") == 0) {
      root = extract(root);
    }
    if(strcmp(command,"end") == 0) break;
  }

  return 0;
}