#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <sstream>
#include <math.h>
#include <string.h>
#include <time.h>

using namespace std;

template <typename T>
class node
{
public:
    T data;
    node<T> *left = NULL;
    node<T> *right = NULL;
    int balance = 0;
    node(T data)
    {
        this->data = data;
    };

    // you can implement other relevant things here
    // TODO
    int depth = 1;
};
template <typename T>
class AVLtree
{
    node<T> *root = NULL;

    /// you can implement other relevant things here
    /// TODO
    int Depth(node<T>* &root) {
        return root->depth;
    }
    int GetBalance(node<T>* &root) {
        int depth_Left, depth_Right;
        if (!root->left) depth_Left = 0;
        else depth_Left = root->left->depth;
        if (!root->right) depth_Right = 0;
        else depth_Right = root->right->depth;
        return depth_Left - depth_Right;
    }
    int update_depth(node<T>* &root) {
        int depth_root, depth_Left, depth_Right;
        if (!root->left) depth_Left = 0;
        else depth_Left = root->left->depth;
        if (!root->right) depth_Right = 0;
        else depth_Right = root->right->depth;
        depth_root = (depth_Left > depth_Right ? depth_Left : depth_Right) + 1;
        return root->depth = depth_root;
    }
    node<T>* rotLeft(node<T>* &root) {
        node<T>* y = root;
        node<T>* x = y->right;
        y->right = x->left;
        x->left = y;
        update_depth(y);
        update_depth(x);
        return x;
    }
    node<T>* rotRight(node<T>* &root) {
        node<T>* y = root;
        node<T>* x = y->left;
        y->left = x->right;
        x->right = y;
        update_depth(y);
        update_depth(x);
        return x;
    }
    node<T>* rotLeftRight(node<T>* &root) {
        node<T>* y = root;
        node<T>* x = y->left;
        node<T>* z = x->right;
        x->right = z->left;
        z->left = x;

        y->left = z->right;
        z->right = y;
        update_depth(y);
        update_depth(x);
        update_depth(z);
        return z;
//        root->left = rotLeft(root->left);
//        return rotRight(root);
    }
    node<T>* rotRightLeft(node<T>* &root) {
        node<T>* y = root;
        node<T>* x = y->right;
        node<T>* z = x->left;
        x->left = z->right;
        z->right = x;

        y->right = z->left;
        z->left = y;
        update_depth(y);
        update_depth(x);
        update_depth(z);
        return z;
//        root->right = rotRight(root->right);
//        return rotLeft(root);
    }
    node<T>* add(node<T>* &root, T &data) {
        if (root == NULL) {
            node<T>* Node = new node<T>(data);
            return Node;
        }
        else {
            if (data >= root->data) {
                root->right = add(root->right, data);
            }
            else {
                root->left = add(root->left, data);
            }
            update_depth(root);
            int balance = GetBalance(root);
            if (balance > 1) {
                if (GetBalance(root->left) >= 0) root = rotRight(root);
                else root = rotLeftRight(root);
            }
            if (balance < -1) {
                if (GetBalance(root->right) <= 0) root = rotLeft(root);
                else root = rotRightLeft(root);
            }
            return root;
        }
    }
    node<T>* find_max(node<T>* &root) {
        if (root == NULL) return NULL;
        if (root->right == NULL) return root;
        return find_max(root->right);
    }
    node<T>* find_min(node<T>* &root) {
        if (root == NULL) return NULL;
        if (root->left == NULL) return root;
        return find_min(root->left);
    }
    node<T>* find_value(node<T>* &root, T &data) {
        if (root == NULL) return NULL;
        if (root->data == data) return root;
        if (data < root->data) return find_value(root->left, data);
        return find_value(root->right, data);
    }
    node<T>* remove(node<T>* &root, T &data){
        if (root == NULL) return NULL;
        if (data < root->data) root->left = remove(root->left, data);
        else {
            if (data > root->data) root->right = remove(root->right, data);
            else {
                if (root->left == NULL && root->right == NULL) {
                    delete root;
                    root = NULL;
                    return NULL;
                }
                if (root->left == NULL) return root->right;
                if (root->right == NULL) return root->left;
                node<T> *y = find_min(root->right);
                root->data = y->data;
                root->right = remove(root->right, root->data);
            }
        }
        update_depth(root);
        int D = Depth(root);
        int Balance = GetBalance(root);
        if (Balance > 1 && GetBalance(root->left) >= 0) return rotRight(root);
        if (Balance > 1 && GetBalance(root->left) < 0) return rotLeftRight(root);
        if (Balance < -1 && GetBalance(root->right) <= 0) return rotLeft(root);
        if (Balance < -1 && GetBalance(root->right) > 0) return rotRightLeft(root);
        return root;
    }
    node<T>* lower_bound(node<T>* &root, T &data) {
        if (root == NULL) return NULL;
        if (root->data < data) return lower_bound(root->right, data);
        node<T> *Res = lower_bound(root->left, data);
        if (Res != NULL) return Res;
        return root;
    }
    node<T>* upper_bound(node<T>* &root, T &data) {
        if (root == NULL) return NULL;
        if (root->data > data) return upper_bound(root->left, data);
        node<T> *Res = upper_bound(root->right, data);
        if (Res != NULL) return Res;
        return root;
    }
    void print(node<T> *&subroot)
    {
        if (subroot == 0)
        {
            cout << '*';
            return;
        }
        cout << subroot->data;
        cout << '(';
        print(subroot->left);
        cout << '|';
        print(subroot->right);
        cout << ')';
        return;
    }
    void PrintLNR(node<T>* &root) {
        if (root == 0) return;
        PrintLNR(root->left);
        cout << root->data << ' ';
        PrintLNR(root->right);
    }

public:
    AVLtree() {}

    // the add function:
    bool empty() {
        return root == NULL;
    }
    bool add(T &data)
    {
        ///if (find_value(root, data) == NULL)
        root = add(root, data);
        return true;
    }
    bool remove(T &data) {
        if (find_value(root, data) == NULL) return false;
        root = remove(root, data);
        return true;
    }
    bool DoLower_bound(T &data, T &Value) {
        node<T>* Res = lower_bound(root, data);
        if (Res == NULL) {
            return false;
        }
        Value = Res->data;
        return true;
    }
    bool DoUpper_bound(T &data, T &Value) {
        node<T>* Res = upper_bound(root, data);
        if (Res == NULL) {
            return false;
        }
        Value = Res->data;
        return true;
    }
    T find_min() {
        return find_min(root)->data;
    }
    T find_max() {
        return find_max(root)->data;
    }
    void print()
    {
        ///print(root);
        PrintLNR(root);
    }
};

#define INP "solve"
#define OUT "solve"
int main(int argc, char* argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);
    //freopen(INP ".inp","r",stdin);
    //freopen(OUT ".out","w",stdout);
	AVLtree<int> ATree;
	while (true) {
        string s;
        cin >> s;
        if (s == "end") break;
        if (s == "insert") {
            int x;
            cin >> x;
            ATree.add(x);
        }
        else {
            int x = ATree.find_max();
            cout << x << '\n';
            ATree.remove(x);
        }
	}
//    while (true) {
//        int Type;
//        cin >> Type;
//        if (Type == 0) break;
//        if (Type == 1) {
//            int x;
//            cin >> x;
//            ATree.add(x);
//            continue;
//        }
//        if (Type == 2) {
//            int x;
//            cin >> x;
//            ATree.remove(x);
//            continue;
//        }
//        if (ATree.empty()) {
//            if (Type > 4) {
//                int x;
//                cin >> x;
//            }
//            cout << "empty" << '\n';
//            continue;
//        }
//        if (Type == 3) {
//            cout << ATree.find_min() << '\n';
//            continue;
//        }
//        if (Type == 4) {
//            cout << ATree.find_max() << '\n';
//            continue;
//        }
//        int x;
//        cin >> x;
//        int Res = -1;
//        if (Type == 5) x++;
//        if (Type <= 6) {
//            if (ATree.DoLower_bound(x, Res)) cout << Res << '\n';
//            else cout << "no" << '\n';
//            continue;
//        }
//        if (Type == 7) x--;
//        if (ATree.DoUpper_bound(x, Res)) cout << Res << '\n';
//        else cout << "no" << '\n';
//    }
    ///ATree.print();
}



Measured memory_bytes: 59796