// A C++ program to demonstrate common Binary Heap Operations
#include<iostream>
#include<climits>
using namespace std;

// Prototype of a utility function to swap two integers
void swap(int *x, int *y);

// A class for Min Heap
class MinHeap
{
    int *harr; // pointer to array of elements in heap
    int capacity; // maximum possible size of min heap
    int heap_size; // Current number of elements in min heap
public:
    // Constructor
    MinHeap(int capacity);
    
    // to heapify a subtree with the root at given index
    void MinHeapify(int );
    
    int parent(int i) { return (i-1)/2; }
    
    // to get index of left child of node at index i
    int left(int i) { return (2*i + 1); }
    
    // to get index of right child of node at index i
    int right(int i) { return (2*i + 2); }
    
    // to extract the root which is the minimum element
    int extractMin();
    
    // Inserts a new key 'k'
    void insertKey(int k);

    // print the array of elements in heap
    void printArray();
};
// Constructor: Builds a heap from a given array a[] of given size
MinHeap::MinHeap(int cap)
{
    heap_size = 0;
    capacity = cap;
    harr = new int[cap];
}

// Inserts a new key 'k'
void MinHeap::insertKey(int k)
{
    if (heap_size == capacity)
    {
        cout << "\nOverflow: Could not insertKey\n";
        return;
    }
    
    // First insert the new key at the end
    //TODO
    
    // Fix the min heap property if it is violated
    //TODO
}

// Method to remove minimum element (or root) from min heap
int MinHeap::extractMin()
{
    if (heap_size <= 0)
        return INT_MAX;
    if (heap_size == 1)
    {
        heap_size--;
        return harr[0];
    }
    
    // Store the minimum value, and remove it from heap
    //TODO
}

//print the array of elements in heap
void MinHeap::printArray()
{
    for(int i = 0; i<heap_size;i++)
        cout<<harr[i]<<endl;
}

// A recursive method to heapify a subtree with the root at given index
// This method assumes that the subtrees are already heapified
void MinHeap::MinHeapify(int i)
{
    //TODO
}

// A utility function to swap two elements
void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

int main()
{
    //We fixed the size of the Heap to 20
    MinHeap h(20);

    string cmd;

    while(cin >> cmd){
        if(cmd == "insertKey"){
            int x;
            cin >> x;
            h.insertKey(x);
        }else if(cmd == "extractMin"){
            cout<<h.extractMin()<<endl;
        }else if(cmd == "printArray"){
            h.printArray();
        }else if(cmd == "exit"){
            return 0;
        }
    }

    return 0;

}