import heapq, sys
sys.stdout = open("priorityqueue.out", "w")
queue = []
operations = open("priorityqueue.in").read().strip().split("\n")
for op in operations:
    op_parsed = op.split()
    if op_parsed[0] == "push":
        heapq.heappush(queue, int(op_parsed[1]))
    elif op_parsed[0] == "extract-min":
        try:
            print(heapq.heappop(queue))
        except IndexError:
            print("*")
    else:
        queue.pop(int(op_parsed[1]) - 1)
        while int(op_parsed[1]) - 1 < len(queue):
            heapq._siftup(queue, int(op_parsed[1]) - 1)
            heapq._siftdown(queue, 0 , int(op_parsed[1]) - 1)
        heapq.heappush(queue, int(op_parsed[2]))