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

#define MAX_COMMAND_NUM 2000000
#define ODD_NUM         1
#define OFF             0
#define ON              1
#define ARRAY_OFFSET    1

int  NewInsertPoint;

static void InsertPorocess(int *heaptree, int key);
static void ExtractPorocess(int *heaptree);
static void UpHeap(int *heaptree, int check_point);
static void DownHeap(int *heaptree);
static void SwapPoint(int *heaptree, int point_1, int point_2);

int main(void)
{
	int key;									/* insert key */
	char command[8];							/* command name */
	int heaptree[MAX_COMMAND_NUM + 1] = {0};	/* heap Tree */
	int loop = 0;
	
	NewInsertPoint = 0;		/* Root point */
	
	/* get Name & time */
	while(((scanf("%s %d", command, &key)) != EOF) && loop <= MAX_COMMAND_NUM)
	{
		if(strncmp(command, "end", 3) == 0) 		/* End Process */
		{
			break;
		}
		else if(strncmp(command, "insert", 6) == 0) 							/* Insert Process */
		{
			InsertPorocess( heaptree, key );
		}
		else if(strncmp(command, "extract", 7) == 0) /* Extract Process */
		{
			ExtractPorocess( heaptree );
		}
		else
		{
			/* error input */
		}
		loop++;
	}
	
    return 0;
}

static void InsertPorocess(int *heaptree, int key)
{
	heaptree[NewInsertPoint] = key;		/* set key value */
	UpHeap(heaptree, NewInsertPoint);	/* sort up heap */
	NewInsertPoint++;
}

static void ExtractPorocess(int *heaptree)
{
	if(NewInsertPoint != 0)				/* data is not empty */
	{
		printf("%d\n", heaptree[0]);
		NewInsertPoint--;
		heaptree[0] = heaptree[NewInsertPoint];
		heaptree[NewInsertPoint] = 0;
		DownHeap(heaptree);
	}

}

static void UpHeap(int *heaptree, int check_point)
{
	int swap_point;
	
	while((check_point != 0))								/* not Root and not finish upheap */
	{
		/* set swap point */
		if(check_point % 2 == ODD_NUM)						/* odd number */
		{
			if(check_point == 1)
			{
				swap_point = 0;
			}
			else
			{
				swap_point = (check_point - ARRAY_OFFSET) / 2;
			}
		}
		else												/* even number */
		{
			swap_point = (check_point / 2) - ARRAY_OFFSET;
		}
		
		/* compare check point and swap point */
		if(heaptree[check_point] > heaptree[swap_point])	/* up point is little */
		{
			SwapPoint(heaptree, check_point, swap_point);	/* swap point heap tree */
			check_point = swap_point;						/* continue upheap */
		}
		else
		{
			break;											/* finish up heap */
		}
	}
}

static void DownHeap(int *heaptree)
{
	int point_l;	/* left point */
	int point_r;	/* right point */
	int check_point;
	
	check_point = 0;											/* Root Point */
	point_l = 1;												/* Root left leaf */
	while((point_l < NewInsertPoint))
	{
		point_r = point_l + 1;									/* set right leaf */
		if(point_r == NewInsertPoint)							/* right leaf is empty */
		{
			if(heaptree[point_l] > heaptree[check_point])
			{
				SwapPoint(heaptree, point_l, check_point);
			}
			break;												/* finish down heap */
		}
		else
		{
			if(heaptree[point_l] > heaptree[point_r])			/* left leaf is bigger than right leaf */
			{
				if(heaptree[point_l] > heaptree[check_point])
				{
					SwapPoint(heaptree, point_l, check_point);
					check_point = point_l;
				}
				else
				{
					break;										/* finish down heap */
				}
			}
			else												/* right leaf is bigger than left leaf */
			{
				if(heaptree[point_r] > heaptree[check_point])
				{
					SwapPoint(heaptree, point_r, check_point);
					check_point = point_r;
				}
				else
				{
					break;										/* finish down heap */
				}
			}
		}
		
		point_l = (check_point * 2) + ARRAY_OFFSET;
	}
}

static void SwapPoint(int *heaptree, int point_1, int point_2)
{
	int swap;
	
	/* exchage two point */
	swap = heaptree[point_1];
	heaptree[point_1] = heaptree[point_2];
	heaptree[point_2] = swap;
}



Measured memory_bytes: 9548