import java.util.*;
public class Main {
    public static int size = 0;
    public static HeapNode root;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int optNum = input.nextInt();
        String line = input.nextLine();
        for (int i = 0; i < optNum; i++) {
            line = input.nextLine();
            if ("top".equals(line)) {
                top();
            } else if ("pop".equals(line)) {
                pop();
            } else {
                push(Integer.parseInt(line.substring(5)));
            }
        }
    }
    public static void top() {
        if (size == 0) {
            System.out.println("empty");
        } else {
            System.out.println(root.val);
        }
    }
    public static void pop() {
        if (size == 0) {
            System.out.println("empty");
        } else {
            System.out.println(root.val);
            //删除root结点，将root左右结点中更大的那个变成根节点
            //1.没有左节点
            if (root.right != null && root.left == null) {
                root = root.right;
            }
            //2.没有右节点
            else if (root.left != null && root.right == null) {
                root = root.left;
            }
            //3.都没有
            else if (root.left == null && root.right == null) {
                root = null;
            }
            //4.都有
            else {
                if (root.left.val > root.right.val) {
                    push(root.right, root.left);
                    root = root.left;
                } else {
                    push(root.left, root.right);
                    root = root.right;
                }
            }
            size--;
        }
    }
    public static void push(int x) {
        if (size == 0) {
            root = new HeapNode(x);
            size++;
            return;
        }
        HeapNode target = new HeapNode(x);
        push(target, root);
        size++;
    }
public static void push(HeapNode target, HeapNode top){
        if(target==null) return;
        //首先看看要去哪边，存在三种情况
        //1.x比top大，它就会成为新的top
        //2.x比top.left和top.right都大，但比top小，那么它会成为新的left或right
        //3.x比top.left或top.right其中之一小，那么它就去大的那边
        //4.x比top.left和top.right都小，就去深度小的子树那边
        int lVal = (top.left==null? Integer.MIN_VALUE:top.left.val);
        int rVal = (top.right==null? Integer.MIN_VALUE:top.right.val);
        //1.如果x比top大
        if(target.val>top.val){
            target.left = top;
            root = target;
        }else if(target.val<=lVal && target.val>rVal){
            if(rVal==Integer.MIN_VALUE){
                //如果右子树是空的
                top.right = target;
            }else{
                //不空的话往左子树加
                push(target,top.left);
            }
        }else if(target.val<=rVal && target.val>lVal){
            if(lVal==Integer.MIN_VALUE){
                //如果左子树是空的
                top.left = target;
            }else{
                //不空的话往右子树加
                push(target,top.right);
            }
        }else if(target.val>rVal){

            if(lVal==Integer.MIN_VALUE){
                top.left = target;
            }else if(rVal==Integer.MIN_VALUE){
                top.right = target;
            }else{
                if(lVal>rVal){
                    push(top.right,target);
                    top.right = target;
                }else {
                    push(top.left,target);
                    top.left = target;
                }
                
            }
        }else {
            if(lVal>rVal){
                push(target,top.right);
            }else{
                push(target,top.left);
            }
        }
    }
}

class HeapNode {
    int val;
    HeapNode left;
    HeapNode right;
    public HeapNode(int val) {
        this.val = val;
    }
}