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

#define MAX_COMMAND_NUM 2000000000

#define PLUS_DEPTH     1
#define MINUS_DEPTH  (-1)

typedef struct ST_TREE_POINT TreePoint_t;

struct ST_TREE_POINT{
	int key;				/* key value */
	int depth;				/* Depth */
	TreePoint_t *top;		/* Top   Point */
	TreePoint_t *left;		/* Left  Point */
	TreePoint_t *right;		/* Right Point */
}AVL_TREE;

static void InsertPorocess(TreePoint_t *ptTreePoint, int key);
static void InsertLeftProcess(TreePoint_t *ptTreePoint, int key, int depth);
static void InsertRightProcess(TreePoint_t *ptTreePoint, int key, int depth);
static void ExtractPorocess(TreePoint_t *ptTreePoint);
static void CompareTreeDepth(TreePoint_t *ptTreePoint, int depth_l, int depth_r);
static void ChangeDepth(TreePoint_t *ptTreePoint, int value);
static void AllFreeProcess(TreePoint_t *ptTreePoint);

int main(void)
{
	int key;							/* insert key */
	int command[8];						/* command name */
	TreePoint_t *ptTreeTemp;			/* Tree Temp Data */
	TreePoint_t *ptRootPoint;			/* Tree Root Point */
	int loop = 0;
	
	/* Init Root Tree */
	ptRootPoint = NULL;
	
	/* get Name & time */
	while(((scanf("%s %d", command, &key)) != EOF) && loop <= MAX_COMMAND_NUM)
	{
		/* set Root point */
		if(ptRootPoint != NULL)
		{
			while(( ptRootPoint->top != NULL ) && ( ptRootPoint->depth != 0 ))
			{
				ptRootPoint = ptRootPoint->top;
			}
		}
		
		if( strcmp(command, "end") == 0 ) /* End Process */
		{
			break;
		}
		else if( strcmp(command, "insert") == 0 ) /* Insert Process */
		{
			InsertPorocess( ptRootPoint, key );
		}
		else if( strcmp(command, "extract") == 0 ) /* Extract Process */
		{
			ExtractPorocess( ptRootPoint );
		}
		else
		{
			/* error input */
		}
		loop++;
	}
	
	/* all free process */
	AllFreeProcess(ptRootPoint);
	
    return 0;
}

static void InsertPorocess(TreePoint_t *ptTreePoint, int key)
{
	TreePoint_t *ptInsertData;			/* Insert Data */
	
	if(ptTreePoint == NULL)
	{
		ptInsertData = (TreePoint_t *)malloc(sizeof(TreePoint_t));
		ptInsertData->key     = key;
		ptInsertData->depth   = 0;
		ptInsertData->top     = NULL;
		ptInsertData->left    = NULL;
		ptInsertData->right   = NULL;

		ptTreePoint = ptInsertData;
	}
	else if(ptTreePoint != NULL)
	{
		if(ptTreePoint->key > key)
		{
			InsertLeftProcess(ptTreePoint, key, 1);
		}
		else
		{
			InsertRightProcess(ptTreePoint, key, 1);
		}
	}
	
}

static void InsertLeftProcess(TreePoint_t *ptTreePoint, int key, int depth)
{
	TreePoint_t *ptInsertData;			/* Insert Data */
	
	if(ptTreePoint->left == NULL)
	{
		ptInsertData = (TreePoint_t *)malloc(sizeof(TreePoint_t));
		ptInsertData->key     = key;
		ptInsertData->depth   = depth;
		ptInsertData->top     = ptTreePoint;
		ptInsertData->left    = NULL;
		ptInsertData->right   = NULL;

		ptTreePoint->left = ptInsertData;
		
		/* if MAX depth change */
		if(ptTreePoint->right == NULL && depth > 1)
		{
			CompareTreeDepth(ptTreePoint->top, depth, 0);
		}
	}
	else
	{
		ptTreePoint = ptTreePoint->left;
		
		if(ptTreePoint->key > key)
		{
			InsertLeftProcess(ptTreePoint, key, (depth + 1));
		}
		else
		{
			InsertRightProcess(ptTreePoint, key, (depth + 1));
		}
	}
}

static void InsertRightProcess(TreePoint_t *ptTreePoint, int key, int depth)
{
	TreePoint_t *ptInsertData;			/* Insert Data */
	
	if(ptTreePoint->right == NULL)
	{
		ptInsertData = (TreePoint_t *)malloc(sizeof(TreePoint_t));
		ptInsertData->key     = key;
		ptInsertData->depth   = depth;
		ptInsertData->top     = ptTreePoint;
		ptInsertData->left    = NULL;
		ptInsertData->right   = NULL;

		ptTreePoint->right = ptInsertData;
		
		/* if MAX depth change */
		if(ptTreePoint->left == NULL && depth > 1)
		{
			CompareTreeDepth(ptTreePoint->top, 0, depth);
		}
	}
	else
	{
		ptTreePoint = ptTreePoint->right;
		
		if(ptTreePoint->key > key)
		{
			InsertLeftProcess(ptTreePoint, key, (depth + 1));
		}
		else
		{
			InsertRightProcess(ptTreePoint, key, (depth + 1));
		}
	}
}

static void ExtractPorocess(TreePoint_t *ptTreePoint)
{
	TreePoint_t * ptTempTree;
	if(ptTreePoint != NULL)
	{
		/* serch max key */
		while(ptTreePoint->right != NULL)
		{
			ptTreePoint = ptTreePoint->right;
		}
		
		printf("%d\n", ptTreePoint->key);
		
		if(ptTreePoint->left != NULL)
		{
			ptTempTree = ptTreePoint->left;
			
			ptTreePoint = ptTreePoint->top;
			free(ptTreePoint->right);
			ptTreePoint->right = ptTempTree;
			ChangeDepth(ptTempTree,  MINUS_DEPTH);
			CompareTreeDepth(ptTreePoint, 0, ptTempTree->depth);
		}
		else
		{
			ptTreePoint = ptTreePoint->top;
			free(ptTreePoint->right);
			CompareTreeDepth(ptTreePoint, 0, ptTreePoint->depth);
		}
	}
}

static void CompareTreeDepth(TreePoint_t *ptTreePoint, int depth_l, int depth_r)
{
	TreePoint_t * ptTempTree;
	TreePoint_t * ptNewTopTree;
	
	if(depth_l == 0)
	{
		ptTempTree = ptTreePoint;
		depth_l = ptTempTree->depth;
		
		/* serch max left depth */
		while(ptTempTree->left != NULL)
		{
			ptTempTree = ptTempTree->left;
			depth_l = ptTempTree->depth;
		}
	}
	else if(depth_r == 0)
	{
		ptTempTree = ptTreePoint;
		depth_r = ptTempTree->depth;
		/* serch max right depth */
		while(ptTempTree->right != NULL)
		{
			ptTempTree = ptTempTree->right;
			depth_r = ptTempTree->depth;
		}
	}
	
	/* equilibrium tree */
	if(depth_r - depth_l >= 2)
	{
		/* right is new Top tree */
		ptNewTopTree = ptTreePoint->right;
		
		/* change Tree top */
		ptNewTopTree->top = ptTreePoint->top;
		ptTempTree = ptNewTopTree->left;
		ptNewTopTree->left = ptTreePoint;
		ptNewTopTree->depth--;
		ChangeDepth(ptNewTopTree->right,  MINUS_DEPTH);
		
		/* change Top to left */
		ptTreePoint->top = ptNewTopTree;
		ptTreePoint->right = ptTempTree;
		ptTreePoint->depth++;
		ChangeDepth(ptTreePoint->left,  PLUS_DEPTH);
	}
	else if(depth_l - depth_r >= 2)
	{
		/* left is new Top tree */
		ptNewTopTree = ptTreePoint->left;
		
		/* change Tree top */
		ptNewTopTree->top = ptTreePoint->top;
		ptTempTree = ptNewTopTree->right;
		ptNewTopTree->right = ptTreePoint;
		ptNewTopTree->depth--;
		ChangeDepth(ptNewTopTree->right,  MINUS_DEPTH);
		
		/* change Top to right */
		ptTreePoint->top = ptNewTopTree;
		ptTreePoint->left = ptTempTree;
		ptTreePoint->depth++;
		ChangeDepth(ptTreePoint->left,  PLUS_DEPTH);
	}
}

static void ChangeDepth(TreePoint_t *ptTreePoint, int value)
{
	ptTempTree->depth += value;
	
	if(ptTreePoint->left != NULL)
	{
		ChangeDepth(ptTreePoint->left, value);
	}
	if(ptTreePoint->right != NULL)
	{
		ChangeDepth(ptTreePoint->right, value);
	}
}

static void AllFreeProcess(TreePoint_t *ptTreePoint)
{
	if(ptTreePoint->left != NULL)
	{
		AllFreeProcess(ptTreePoint->left);
	}
	if(ptTreePoint->right != NULL)
	{
		AllFreeProcess(ptTreePoint->right);
	}
	
	free(ptTreePoint);
}


