fun main(args: Array<String>) {
    val tree = CompleteBinaryTree(2000000)
    while (true) {
        val input = readLine()?.split(" ".toRegex()) ?: return
        when (input[0]) {
            "insert" -> tree.insert(input[1].toInt())
            "extract" -> println(tree.extract())
            "end" -> return
        }
    }
}

fun IntArray.swap(i: Int, j: Int) {
    val tmp = this[i]
    this[i] = this[j]
    this[j] = tmp
}

class CompleteBinaryTree(size: Int) {
    private val array = IntArray(size + 1)
    var heapSize = 0
        private set

    fun insert(key: Int) {
        heapSize++
        heapIncreaseKey(heapSize, key)
    }

    private fun heapIncreaseKey(index: Int, key: Int) {
        array[index] = key
        var i = index
        while (i > 1 &&  array[parent(i)] < array[i]) {
            array.swap(i, parent(i))
            i = parent(i)
        }
    }

    fun extract(): Int {
        val max = array[1]
        array[1] = array[heapSize]
        heapSize--
        maxHeapify(1)
        return max
    }

    fun maxHeapify(index: Int) {
        val l = left(index)
        val r = right(index)
        var largest = if (l <= heapSize && array[l] > array[index]) {
            l
        } else {
            index
        }
        if (r <= heapSize && array[r] > array[largest]) {
            largest = r
        }
        if (largest != index) {
            array.swap(index, largest)
            maxHeapify(largest)
        }
    }

    private fun parent(index: Int) = index / 2
    private fun left(index: Int) = 2 * index
    private fun right(index: Int) = 2 * index + 1
}

