////////////////////////////////////////
//ALDS1_9_A:   Complete Binary Tree
//ALDS1_9_B:   Maximum Heap
//ALDS1_9_C:   Priority Queue
////////////////////////////////////////

#include <iostream>
#include <algorithm> // next_permutation
#include <iomanip>
#include <cmath>
#include <vector>
#include <sstream>
#include <string>
#include <cstdio>
#include <stack>
#include <queue>
#include <list>
#include <numeric> //accumulate
//#include <unordered_map> //???????????\??¢??°
#include <fstream> //ifstream, ofstream

//#define NDEBUG //NDEBUG???#include <cassert>???????????????????????????????????´???assert?????????????????????????????????NDEBUG?????????????????????????????????????????????
#include <cassert> //assert


using namespace std;

//???????????°??????TEST????????????????????¬???????????????????????????????????¢????????????
#define TEST //*******************************************************************************************************************************************
//?????????????????¨??§?????\????????????????????????????????°?????????????¨???????????????????dout???????????????????????§???????????¬??????????????????????????????????????????
//??????????????????????????????????????????????????????????§?CPU???????£??????????????????§???TLE?????????????????????????????????????????§????????¨???                           ????????????????????????cerr????????£????????????????????????????????????
#ifdef TEST
#define dout cout
#define din cin
#else
stringstream dummy; //???????????°??????dout?????????????????????????????????
#define dout dummy.str(""); dummy.clear(stringstream::goodbit); dummy //dummy?????????????????????????????????????????¨?????¢?????¢???????????????
//???????????¨??????????????????goodbit?????????????????????????????¨???????????´????????????????????????????????¨?????°?????????????????§???????????????????????????????????? http://d.hatena.ne.jp/linden/20060427/p1
#endif

//?¨??????????????????????????????????????????????????????´??????OUTPUTFILE????????????????????¬???????????????????????????????????¢????????????
//#define OUTPUTFILE "output.txt" //*******************************************************************************************************************************************
#ifdef OUTPUTFILE
#define dout outputfile //??¨????????????TLE????????§?????????dout?????¨??¨??????????????¢????????????????????????????????????????????§????¨????????????´??????????????£??????????????????????¨?????????????????????????????????????????????§?????????????????????
ofstream outputfile(OUTPUTFILE);
#define OutputFilePath "/Users/Nag/Documents/Prgm/Test/DerivedData/Test/Build/Products/Debug/output.txt"
#endif

//?¨??????\???????????????????????????????????????????????´??????INPUTFROMTEXTFILE????????????????????¬???????????????????????????????????¢????????????
//#define INPUTFILE "input.txt" //*******************************************************************************************************************************************
#ifdef INPUTFILE
#define din inputfile
ifstream inputfile(INPUTFILE);
#endif


#define disp(A) dout << #A << " = " << (A) << endl
#define disP(A) dout << setw(3) << (A) << " " // << setw(3) ??????????????\????????????
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)

#define dispAll(A,n) dout << #A << " = "; rep(j, 0, (n)) {disP(A[j]);} dout << endl

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef unsigned long long ll;

const int INF = 1e9-1;

int maxHeap[2000001];
int H;

int parentOf(int i) {
    return i/2;
}

int leftChildOf(int i) {
    return i*2;
}

int rightChildOf(int i) {
    return i*2+1;
}

void maxHeapify(int i) {
    //    dout << "---------\n";
    //    dout << "maxHeapify( " << i << " ) : " << "key = " << maxHeap[i] << "\n";
    
    int largest;
    int left = leftChildOf(i);
    int right = rightChildOf(i);
    
    //i,?????????,????????????3????????????????????§??????????????¢???
    if( left<=H && maxHeap[left]>maxHeap[i] ) largest = left;
    else largest = i;
    
    if( right<=H && maxHeap[right]>maxHeap[largest] ) largest = right;
    
    if( largest != i ) { //?????§????????????i??§???????????°???i??¨largest?????????swap?????????largest??\??????????§????
        int tmp = maxHeap[i];
        maxHeap[i] = maxHeap[largest];
        maxHeap[largest] = tmp;
        
        maxHeapify(largest); //recursive call
    }
}

void buildMaxHeap() {
    for(int i=H/2; i>0; i--) {
        maxHeapify(i);
    }
}


void display() {
    string parentKeyStr;
    string leftKeyStr;
    string rightKeyStr;
    ostringstream oss;
    
    rep(i,1,H+1) {
        if(parentOf(i)>0) {
            parentKeyStr = "parent key = ";
            oss << maxHeap[parentOf(i)];
            parentKeyStr += oss.str();
            parentKeyStr += ", ";
            oss.str("");
        } else parentKeyStr = "";
        
        if(leftChildOf(i)<=H) {
            leftKeyStr = "left key = ";
            oss << maxHeap[leftChildOf(i)];
            leftKeyStr += oss.str();
            leftKeyStr += ", ";
            oss.str("");
        } else leftKeyStr = "";
        
        if(rightChildOf(i)<=H) {
            rightKeyStr = "right key = ";
            oss << maxHeap[rightChildOf(i)];
            rightKeyStr += oss.str();
            rightKeyStr += ", ";
            oss.str("");
        } else rightKeyStr = "";
        
        dout << "node " << i << ": key = " << maxHeap[i] << ", "
        << parentKeyStr << leftKeyStr << rightKeyStr << endl;
    }
}


void insert(int x) {
    H++;
    maxHeap[H] = x;
    
    int i = H;
    
    while(i>1 && maxHeap[parentOf(i)] < maxHeap[i]) {
        swap(maxHeap[parentOf(i)], maxHeap[i]);
        i = parentOf(i);
    }
}


int main(){
    H = 0;
    
    string command;
    int x;
    while(1) {
//        dout << "---------------------------------\n";
        din >> command;
        
        if(command[0]=='i') {
            cin >> x;
            
//            dout << "insert " << x << endl;
            
            insert(x);
//            maxHeap[++H] = x;
//            buildMaxHeap();
        }
        else if(command[1]=='x') {
            
//            dout << "extract " << endl;
            dout << maxHeap[1] << endl;
            
            //????°????????´??????????????????£?????????????§????
            maxHeap[1] = maxHeap[H--];
            maxHeapify(1);
        }
        else {
            break;
        }
        
//        disp(H);
//        dispAll(maxHeap, 20);
//        display();
    }
    
    
    
    
#ifdef INPUTFILE
    inputfile.close();
#endif
    
#ifdef OUTPUTFILE
    outputfile.close();
    cout << "\"" << OutputFilePath << "\"" << endl;
#endif
    
    return 0;
}

Measured memory_bytes: 7008