//*****************************************************************************/
// include
//*****************************************************************************/
#include <stdio.h>

//*****************************************************************************/
// define
//*****************************************************************************/
#define COMMAND_MAXLEN ( ( int ) 8 )
#define QDEPTH ( ( int ) 2000000 )

//*****************************************************************************/
// プロトタイプ宣言
//*****************************************************************************/
void insert( char* pS, int k );
int extractMax( char* pS );
void swap( int x, int y );
int getBigElementIndex( int x, int y );

//*****************************************************************************/
// グローバル変数
//*****************************************************************************/
int S[QDEPTH] = {};		// 優先度付きキュー
int index = 0;			// 優先度付きキューのインデックス

//*****************************************************************************/
// @brief  メイン関数
// @param  無し
// @return 正常終了なら0、異常終了なら-1
//*****************************************************************************/
int main( void )
{
	char command[COMMAND_MAXLEN] = {};	// 入力されたコマンド
	int k = 0;							// 入力された要素

	while( 1 )
	{
		scanf( "%8s", &command[0] );

		if( !strcmp( command, "insert" ) )
		{
			// 入力が"insert"
			scanf( "%d", &k );
			insert( &S[0], k );
		}
		else if( !strcmp( command, "extract" ) )
		{
			// 入力が"extract"
			printf( "%d\n", extractMax( &S[0] ) );
		}
		else
		{
			// 入力が"end"
			break;
		}
	}
	return 0;
}

//*****************************************************************************/
// @brief  優先度付きキューに要素を挿入する
// @param  pS : 優先度付きキューへのポインタ
// @param  k : 挿入する要素
// @return 無し
//*****************************************************************************/
void insert( char* pS, int k )
{
	int leaf = 0;
	int node = 0;

	// 素直にキューへ要素を挿入
	index++;
	S[index] = k;

	// ヒープソート
	leaf = index;
	node = leaf / 2;
	while( (S[leaf] > S[node]) && leaf > 1 )
	{
		swap( leaf, node );
		leaf = node;
		node = leaf / 2;
	}
}

//*****************************************************************************/
// @brief  優先度付きキューに積んだ要素のうち、最大値の要素を返す
// @param  pS : 優先度付きキューへのポインタ
// @return 優先度付きキューに積んだ最大値の要素
//*****************************************************************************/
int extractMax( char* pS )
{
	int i = 1;
	int maxIndex = 0;
	int left = 0;
	int right = 0;
	int maxElement = S[1];
	
	S[1] = S[index];
	index--;
	
	// ヒープの再構築
	while( (i * 2) <= index)
	{
		left = i * 2;
		right = left + 1;
		maxIndex = ( right <= index ) ? getBigElementIndex( left, right ) : left;
		
		if( getBigElementIndex( maxIndex, i ) == maxIndex )
		{
			swap( maxIndex, i );
			i = maxIndex;
		}
		else
		{
			break;
		}
	}
	return maxElement;
}

//*****************************************************************************/
// @brief  引数で指定されたインデックスに積まれている要素を交換する
// @param  x : 優先度付きキューのインデックス
// @param  y : 優先度付きキューのインデックス
// @return 無し
//*****************************************************************************/
void swap( int x, int y )
{
	int temp = S[x];
	
	S[x] = S[y];
	S[y] = temp;
}

//*****************************************************************************/
// @brief  優先度付きキュー内の要素のうち、大きい値が積まれているインデックスを返す
// @param  x : 優先度付きキューのインデックス
// @param  y : 優先度付きキューのインデックス
// @return xとyのうち、値が大きい方のインデックス
//*****************************************************************************/
int getBigElementIndex( int x, int y )
{
	return ( S[x] > S[y] ) ? x : y ;
}



Measured memory_bytes: 5592