#include "stdafx.h"
#include<iostream>
#include<vector>
#include<string>

using namespace std;

vector<int> heap;
vector<int> heapmax;
void siftUp(int v) {
    if (v == 0) return;
    int p = (v - 1) / 2; //родитель
    if (heap[v] < heap[p]) {
        swap(heap[v], heap[p]);
        siftUp(p);
    }
}
void siftDown(int v) {
    int left = 2 * v + 1;
    int right = 2 * v + 2;
    if (left >= heap.size()) return;
    if (left == heap.size() - 1) right = left;
    int imax = heap[left] < heap[right] ? left : right;
    if (heap[v] > heap[imax]) {
        swap(heap[v], heap[imax]);
        siftDown(imax);
    }

}
void siftUpMax(int v) {
    if (v == 0) return;
    int p = (v - 1) / 2; //родитель
    if (heapmax[v] > heapmax[p])
    {
        swap(heapmax[v], heapmax[p]);
        siftUpMax(p);
    }
}
void siftDownMax(int v)
{
    int left = 2 * v + 1;
    int right = 2 * v + 2;
    if (left >= heapmax.size()) return;
    if (left == heapmax.size() - 1) right = left;
    int imax = heapmax[left] > heapmax[right] ? left : right;
    if (heapmax[v] < heapmax[imax])
    {
        swap(heapmax[v], heapmax[imax]);
        siftDownMax(imax);
    }
}


int main() {
    setlocale(LC_CTYPE, "rus");
    string str;
    cout << "ADD <number> - добавляет новый элемент в heap и heapmax\nMIN - выводит минимальный элемент из heap" << endl
        << "MAX - выводит максимальный элемент из heapmax\nCLEAR - очищает heap и heapmax" << endl;
    while (cin >> str) {
        if (str == "ADD") {
            int x = 0;
            cin >> x;
            heap.push_back(x);
            siftUp(heap.size() - 1);
            heapmax.push_back(x);
            siftUpMax(heapmax.size() - 1);
        }
        else if (str == "MIN") {
            if (!heap.empty()) {
                cout << heap[0] << '\n';
                heap[0] = heap.back();
                heap.pop_back();
                siftDown(0);
            }
            else {
                cout << "CANNOT\n";
            }
        }
        else if (str == "MAX")
        {
            if (!heap.empty())
            {
                cout << heapmax[0] << '\n';
                heapmax[0] = heapmax.back();
                heapmax.pop_back();
                siftDownMax(0);
            }
            else
            {
                cout << "CANNOT\n";
            }
        }
        else if (str == "CLEAR") {
            heap = vector<int>();
            heapmax = vector<int>();
        }
    }

    return 0;
}