CodeEff/ECCO huggingface dataset:
# Original solution
import sys
INFTY = 1<<30
class MaxHeap():
    def __init__(self, a, h):
        self.a = a
        self.h = h
        
    def parent(self, i):
        return i//2
        
    def left(self, i):
        return 2 * i

    def right(self, i):
        return 2 * i + 1

    def maxHeapify(self, i):
        l = self.left(i)
        r = self.right(i)
        if l <= self.h and self.a[l] > self.a[i]:
            largest = l
        else:
            largest = i
        if r <= self.h and self.a[r] > self.a[largest]:
            largest = r
        if largest != i:
            self.a[i], self.a[largest] = self.a[largest], self.a[i]
            self.maxHeapify(largest)

    def extract(self):
        if self.h < 1:
            return -INFTY
        maxv = self.a[1]
        self.a[1] = self.a[self.h]
        self.h -= 1
        self.maxHeapify(1)
        return maxv
        
    def increaseKey(self, i, k):
        if k < self.a[i]:
            return
        self.a[i] = k
        while i > 1 and self.a[i//2] < self.a[i]:
            self.a[i], self.a[i//2] = self.a[i//2], self.a[i]
            i = i // 2

    def insert(self, k):
        self.h += 1
        self.a[self.h] = -INFTY
        self.increaseKey(self.h, k)

if __name__ == '__main__':
    a = [None] * (2000000 + 1)
    x = MaxHeap(a, 0)
    ret = [None] * (2000000 + 1)
    i = 0
    coms = sys.stdin.readlines()
    for com in coms:
        if com[0] == "i":
            k = int(com.split()[1])
            x.insert(k)
        elif com[0:2] == "ex":
            ret[i] = x.extract()
            i += 1
        else:
            sys.stdout.write("\n".join([str(s) for s in ret[:i]]))
            print()


    

# Optimized solution
import sys
INFTY = 1<<30
a = [None] * (2000000 + 1)
h = 0
ret = [None] * (2000000 + 1)
i = 0

def left(i):
    return 2 * i

def right(i):
    return 2 * i + 1

def maxHeapify(i):
    global a, h
    l = left(i)
    r = right(i)
    if l <= h and a[l] > a[i]:
        largest = l
    else:
        largest = i
    if r <= h and a[r] > a[largest]:
        largest = r
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        maxHeapify(largest)

def extract():
    global a, h
    if h < 1:
        return -INFTY
    maxv = a[1]
    a[1] = a[h]
    h -= 1
    maxHeapify(1)
    return maxv
    
def increaseKey(i, k):
    global a
    if k < a[i]:
        return
    a[i] = k
    while i > 1 and a[i//2] < a[i]:
        a[i], a[i//2] = a[i//2], a[i]
        i = i // 2

def insert(k):
    global a, h
    h += 1
    a[h] = -INFTY
    increaseKey(h, k)

coms = sys.stdin.readlines()
for com in coms:
    if com[0] == "i":
        k = int(com.split()[1])
        insert(k)
    elif com[0:2] == "ex":
        ret[i] = extract()
        i += 1
    else:
        sys.stdout.write("\n".join([str(s) for s in ret[:i]]))
        print()
# Original solution
import sys
INFTY = 1<<30
a = [None] * (2000000 + 1)
h = 0
ret = [None] * (2000000 + 1)
i = 0

def left(i):
    return 2 * i

def right(i):
    return 2 * i + 1

def maxHeapify(i):
    global a, h
    l = left(i)
    r = right(i)
    if l <= h and a[l] > a[i]:
        largest = l
    else:
        largest = i
    if r <= h and a[r] > a[largest]:
        largest = r
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        maxHeapify(largest)

def extract():
    global a, h
    if h < 1:
        return -INFTY
    maxv = a[1]
    a[1] = a[h]
    h -= 1
    maxHeapify(1)
    return maxv
    
def increaseKey(i, k):
    global a
    if k < a[i]:
        return
    a[i] = k
    while i > 1 and a[i//2] < a[i]:
        a[i], a[i//2] = a[i//2], a[i]
        i = i // 2

def insert(k):
    global a, h
    h += 1
    a[h] = -INFTY
    increaseKey(h, k)

coms = sys.stdin.readlines()
for com in coms:
    if com[0] == "i":
        k = int(com.split()[1])
        insert(k)
    elif com[0:2] == "ex":
        ret[i] = extract()
        i += 1
    else:
        sys.stdout.write("\n".join([str(s) for s in ret[:i]]))
        print()


    

# Optimized solution
import sys
INFTY = 1<<30
a = [None] * 2000001
h = 0
ret = [] 

def maxHeapify(i):
    global a, h
    l = 2 * i
    r = 2 * i + 1
    if l <= h and a[l] > a[i]:
        largest = l
    else:
        largest = i
    if r <= h and a[r] > a[largest]:
        largest = r
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        maxHeapify(largest)

def extract():
    global a, h
    if h < 1:
        return -INFTY
    maxv = a[1]
    a[1] = a[h]
    h -= 1
    maxHeapify(1)
    return maxv
    
def increaseKey(i, k):
    global a
    if k < a[i]:
        return
    a[i] = k
    while i > 1 and a[i//2] < a[i]:
        a[i], a[i//2] = a[i//2], a[i]
        i = i // 2

def insert(k):
    global a, h
    h += 1
    a[h] = -INFTY
    increaseKey(h, k)

for com in sys.stdin.readlines():
    if com[0] == "i":
        insert(int(com[7:]))
    elif com[1] == "x":
        ret.append(extract()) 
    else:
        print(("\n".join([str(s) for s in ret])))
        # print()
# Original solution
import sys
from collections import deque
INFTY = 1<<30
a = [None] * 2000001
h = 0
ret = deque([])

def maxHeapify(i):
    global a, h
    l = 2 * i
    r = 2 * i + 1
    if l <= h and a[l] > a[i]:
        largest = l
    else:
        largest = i
    if r <= h and a[r] > a[largest]:
        largest = r
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        maxHeapify(largest)

def extract():
    global a, h
    if h < 1:
        return -INFTY
    maxv = a[1]
    a[1] = a[h]
    h -= 1
    maxHeapify(1)
    return maxv
    
def increaseKey(i, k):
    global a
    if k < a[i]:
        return
    a[i] = k
    while i > 1 and a[i//2] < a[i]:
        a[i], a[i//2] = a[i//2], a[i]
        i = i // 2

def insert(k):
    global a, h
    h += 1
    a[h] = -INFTY
    increaseKey(h, k)

i = 0
for com in sys.stdin.readlines():
    if com[0] == "i":
        insert(int(com[7:]))
    elif com[1] == "x":
        ret.append(extract())
    else:
        sys.stdout.writelines("\n".join([str(s) for s in ret]))
        print()

# Optimized solution
from sys import stdin, exit
 
def max_heapify(a, i):
    heap_size = a[0]
 
    L = 2*i
    R = 2*i + 1
    if L <= heap_size and a[L] > a[i]:
        largest = L
    else:
        largest = i
    if R <= heap_size and a[R] > a[largest]:
        largest = R
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        max_heapify(a, largest)
 
 
def main():
    heap = [-1] * 2000001
    heap[0] = 1
    for cmd in stdin:
        if cmd[0] == 'i':
            heap[0] += 1
            i = heap[0]
            heap[i] = int(cmd[7:])
 
            half = i // 2
            while i > 1 and heap[half] < heap[i]:
                heap[i], heap[half] = heap[half], heap[i]
                i //= 2
                half = i // 2
        elif cmd[1] == 'x':
            print((heap[1]))
            heap[1] = heap[heap[0]]
            heap[0] -= 1
            max_heapify(heap, 1)
        elif cmd[1] == 'n':
            exit(0)
 
 
main()
# Original solution
from sys import stdin, exit
 
def max_heapify(a, i):
    heap_size = a[0]
 
    L = 2*i
    R = 2*i + 1
    if L <= heap_size and a[L] > a[i]:
        largest = L
    else:
        largest = i
    if R <= heap_size and a[R] > a[largest]:
        largest = R
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        max_heapify(a, largest)
 
 
def main():
    heap = [-1] * 2000001
    heap[0] = 1
    for cmd in stdin:
        if cmd[0] == 'i':
            heap[0] += 1
            i = heap[0]
            heap[i] = int(cmd[7:])
 
            half = i // 2
            while i > 1 and heap[half] < heap[i]:
                heap[i], heap[half] = heap[half], heap[i]
                i //= 2
                half = i // 2
        elif cmd[1] == 'x':
            print((heap[1]))
            heap[1] = heap[heap[0]]
            heap[0] -= 1
            max_heapify(heap, 1)
        elif cmd[1] == 'n':
            exit(0)
 
 
main()

# Optimized solution
from sys import stdin, stdout, exit
  
def max_heapify(a, i):
    heap_size = a[0]
  
    L = 2*i
    R = 2*i + 1
    if L <= heap_size and a[L] > a[i]:
        largest = L
    else:
        largest = i
    if R <= heap_size and a[R] > a[largest]:
        largest = R
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        max_heapify(a, largest)
  
  
def main():
    ret = []
    heap = [-1] * 2000001
    heap[0] = 1
    for cmd in stdin:
        if cmd[0] == 'i':
            heap[0] += 1
            i = heap[0]
            heap[i] = int(cmd[7:])
  
            half = i // 2
            while i > 1 and heap[half] < heap[i]:
                heap[i], heap[half] = heap[half], heap[i]
                i //= 2
                half = i // 2
        elif cmd[1] == 'x':
            ret.append(heap[1])
            heap[1] = heap[heap[0]]
            heap[0] -= 1
            max_heapify(heap, 1)
        elif cmd[1] == 'n':
            stdout.writelines("\n".join([str(s) for s in ret]))
            print()
            exit(0)
  
  
main()
# Original solution
from sys import stdin, stdout, exit
  
def max_heapify(a, i):
    heap_size = a[0]
  
    L = 2*i
    R = 2*i + 1
    if L <= heap_size and a[L] > a[i]:
        largest = L
    else:
        largest = i
    if R <= heap_size and a[R] > a[largest]:
        largest = R
    if largest != i:
        a[i], a[largest] = a[largest], a[i]
        max_heapify(a, largest)
  
  
def main():
    ret = []
    heap = [-1] * 2000001
    heap[0] = 1
    for cmd in stdin:
        if cmd[0] == 'i':
            heap[0] += 1
            i = heap[0]
            heap[i] = int(cmd[7:])
  
            half = i // 2
            while i > 1 and heap[half] < heap[i]:
                heap[i], heap[half] = heap[half], heap[i]
                i //= 2
                half = i // 2
        elif cmd[1] == 'x':
            ret.append(heap[1])
            heap[1] = heap[heap[0]]
            heap[0] -= 1
            max_heapify(heap, 1)
        elif cmd[1] == 'n':
            stdout.writelines("\n".join([str(s) for s in ret]))
            print()
            exit(0)
  
  
main()

# Optimized solution
import heapq
import sys

h = []

for com in sys.stdin.readlines():
    if com[0] == "i":
        heapq.heappush(h, -int(com[7:]))
    elif com[1] == "x":
        print((-heapq.heappop(h)))
# Original solution
import sys


def max_heapify(a, i):
    h = len(a)
    l = 2 * i + 1
    r = 2 * i + 2
    if l < h and a[l] > a[i]:
        largest = l
    else:
        largest = i
    if r < h and a[r] > a[largest]:
        largest = r

    if largest != i:
        tmp = a[i]
        a[i] = a[largest]
        a[largest] = tmp
        max_heapify(a, largest)


def build_max_heap(a):
    h = len(a)
    for i in range(h // 2 - 1, -1, -1):
        max_heapify(a, i)


def extract_max(a):
    max = a[0]
    a[0] = a[-1]
    a.pop()
    build_max_heap(a)
    return max


def insert(a, n):
    i = len(a)
    a.append(n)
    while i > 0:
        p = int((i + 1) / 2) - 1
        v = a[i]
        pv = a[p]
        if pv < v:
            a[p] = v
            a[i] = pv
            i = p
        else:
            break


heap = []
while True:
    cmd = input().split()
    if cmd[0] == "end":
        break
    elif cmd[0] == "extract":
        print((extract_max(heap)))
    elif cmd[0] == "insert":
        insert(heap, int(cmd[1]))


# Optimized solution
def extract_max(A):
    x = A[0]
    A[0] = A[-1]
    A.pop()
    H = len(A)
    i = 0
    while i < H:  # ???????????????
        v = A[i]
        rv = 0
        lv = 0
        r = (i + 1) * 2
        l = r - 1
        if l < H:
            lv = A[l]
            if r < H:
                rv = A[r]

        if v < lv and lv > rv:
            A[l] = v
            A[i] = lv
            i = l
        elif v < rv:
            A[r] = v
            A[i] = rv
            i = r
        else:
            break
    return x

def insert(a, n):
    i = len(a)
    a.append(n)
    while i > 0:
        p = int((i + 1) / 2) - 1
        v = a[i]
        pv = a[p]
        if pv < v:
            a[p] = v
            a[i] = pv
            i = p
        else:
            break


heap = []
while True:
    cmd = input().split()
    if cmd[0] == "end":
        break
    elif cmd[0] == "extract":
        print((extract_max(heap)))
    elif cmd[0] == "insert":
        insert(heap, int(cmd[1]))
# Original solution
def extract_max(A):
    x = A[0]
    A[0] = A[-1]
    A.pop()
    H = len(A)
    i = 0
    while i < H:  # ???????????????
        v = A[i]
        rv = 0
        lv = 0
        r = (i + 1) * 2
        l = r - 1
        if l < H:
            lv = A[l]
            if r < H:
                rv = A[r]

        if v < lv and lv > rv:
            A[l] = v
            A[i] = lv
            i = l
        elif v < rv:
            A[r] = v
            A[i] = rv
            i = r
        else:
            break
    return x

def insert(a, n):
    i = len(a)
    a.append(n)
    while i > 0:
        p = int((i + 1) / 2) - 1
        v = a[i]
        pv = a[p]
        if pv < v:
            a[p] = v
            a[i] = pv
            i = p
        else:
            break


heap = []
while True:
    cmd = input().split()
    if cmd[0] == "end":
        break
    elif cmd[0] == "extract":
        print((extract_max(heap)))
    elif cmd[0] == "insert":
        insert(heap, int(cmd[1]))


# Optimized solution
import sys


def extract_max(A):
    x = A[0]
    A[0] = A[-1]
    A.pop()
    H = len(A)
    i = 0
    while i < H:
        v = A[i]
        rv = 0
        lv = 0
        r = (i + 1) * 2
        l = r - 1
        if l < H:
            lv = A[l]
            if r < H:
                rv = A[r]

        if v < lv and lv > rv:
            A[l] = v
            A[i] = lv
            i = l
        elif v < rv:
            A[r] = v
            A[i] = rv
            i = r
        else:
            break
    return x


def insert(a, n):
    i = len(a)
    a.append(n)
    while i > 0:
        p = int((i + 1) / 2) - 1
        v = a[i]
        pv = a[p]
        if pv < v:
            a[p] = v
            a[i] = pv
            i = p
        else:
            break


def main():
    istr = sys.stdin.read()
    cmds = list(istr.splitlines())
    S = []
    for cmd in cmds:  # input()
        if cmd[0] == "i":
            insert(S, int(cmd[7:]))

        elif cmd == "extract":
            a = extract_max(S)
            print(a)

        elif cmd == "end":
            break


if __name__ == '__main__':
    main()
# Original solution
def max_heapify(A, i):
	l = i * 2 
	r = i * 2 + 1
	largest = i
	if l < len(A):
		if A[l] > A[largest]:
			largest = l
	if r < len(A):
		if A[r] > A[largest]:
			largest = r
	if largest != i:
		A[i], A[largest] = A[largest], A[i]
		max_heapify(A, largest)
def build_max_heap(A):
	for i in range(int(len(A) / 2), 0, -1):
		max_heapify(A, i)
def insert(A, k):
	A.append(k)
def extract_max(A):
	build_max_heap(A)
	k = A.pop(1)
	return k

A = [None]
while True:
	o = list(map(str, input().split()))
	if o[0] == "insert":
		insert(A, int(o[1]))
	elif o[0] == "extract":
		print((extract_max(A)))
	else:
		break

# Optimized solution

def insert(A, k):
	i = len(A)
	A.append(k)
	while i != 0:
		j = int((i - 1) / 2)
		if A[j] < A[i]:
			A[i], A[j] = A[j], A[i]
		i = j
def extract_max(A):
	k = A[0]
	A[0] = A[-1]
	A.pop()
	n = len(A)
	p = 0
	while True:
		c = 2 * p + 1
		if c >= n:
			break
		if c < n - 1 and A[c] < A[c + 1]:
			c += 1
		if A[p] < A[c]:
			A[p], A[c] = A[c], A[p]
		p = c
	return k

A = []
while True:
	o = list(map(str, input().split()))
	if o[0] == "insert":
		insert(A, int(o[1]))
	elif o[0] == "extract":
		print((extract_max(A)))
	else:
		break
# Original solution
import heapq

def main():
    q = []
    heapq.heapify(q)
    while True:
        s = input().split()
        if s[0] == 'end':
            break
        elif s[0] == 'insert':
            heapq.heappush(q, (-int(s[1]), int(s[1])))
        else:
            p = heapq.heappop(q)
            print((p[1]))

if __name__ == '__main__':
    main()


# Optimized solution
import heapq

def main():
    q = []
    heapq.heapify(q)
    while True:
        s = input().split()
        if s[0] == 'end':
            break
        elif s[0] == 'insert':
            heapq.heappush(q, -int(s[1]))
        else:
            p = heapq.heappop(q)
            print((-p))

if __name__ == '__main__':
    main()
# Original solution
def maxHeapify(i, node_list):
    n = len(node_list)
    if 2*i+1 < n and node_list[2*i+1] > node_list[i]:
        i_largest = 2*i+1
        # node_list[i], node_list[2*i+1] = node_list[2*i+1], node_list[i]
    else:
        i_largest = i
    if 2*i+2 < n and node_list[2*i+2] > node_list[i_largest]:
        i_largest = 2*i+2
        # node_list[i], node_list[2*i+2] = node_list[2*i+2], node_list[i]

    if i_largest != i:
        node_list[i], node_list[i_largest] = node_list[i_largest], node_list[i]
        maxHeapify(i_largest, node_list)

def insert_heap(i, node_list):
    node_list.append(i)
    n = len(node_list)
    for i in range(n//2, -1, -1):
        maxHeapify(i, node_list)

def extract_heap(node_list):
    print((node_list[0]))
    pop = node_list.pop()
    n = len(node_list)
    if n != 0:
        node_list[0] = pop
    for i in range(n//2, -1, -1):
        maxHeapify(i, node_list)

import sys
input_list = sys.stdin.readlines()
node_list = []
for line in input_list:
    line = line.split()
    if line[0] == 'end':
        break
    elif line[0] == 'extract':
        extract_heap(node_list)
    else:
        insert_heap(int(line[1]), node_list)


# Optimized solution
def maxHeapify(i, node_list):
    n = len(node_list)
    if 2*i+1 < n and node_list[2*i+1] > node_list[i]:
        i_largest = 2*i+1
    else:
        i_largest = i
    if 2*i+2 < n and node_list[2*i+2] > node_list[i_largest]:
        i_largest = 2*i+2

    if i_largest != i:
        node_list[i], node_list[i_largest] = node_list[i_largest], node_list[i]
        maxHeapify(i_largest, node_list)

def insert_heap(i, node_list):
    node_list.append(i)
    k = len(node_list) - 1
    while(node_list[k] > node_list[(k-1)//2] and k > 0):
        node_list[k], node_list[(k-1)//2] = node_list[(k-1)//2], node_list[k]
        k = (k-1)//2


def extract_heap(node_list):
    print((node_list[0]))
    pop = node_list.pop()
    n = len(node_list)
    if n != 0:
        node_list[0] = pop
        maxHeapify(0, node_list)

import sys
input_list = sys.stdin.readlines()
node_list = []
for line in input_list:
    line = line.split()
    if line[0] == 'end':
        break
    elif line[0] == 'extract':
        extract_heap(node_list)
    else:
        insert_heap(int(line[1]), node_list)
# Original solution
import sys
readline = sys.stdin.readline
def maxHeapify(A, i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < n and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r < n and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        maxHeapify(A, largest)
def insert(S, k):
    S.append(k)
    i = n - 1
    while i > 0 and S[i] > S[(i - 1) // 2]:
        S[i], S[(i - 1) // 2] = S[(i - 1) // 2], S[i]
        i = (i - 1) // 2
def extractMax(S):
    if len(S) == 1:
        return S.pop()
    ans = S[0]
    S[0] = S.pop()
    maxHeapify(S, 0)
    return ans
A = []
n = 0
while True:
    s = readline()
    if s[2] == "d":
        break
    elif s[2] == "t":
        n -= 1
        print((extractMax(A)))
    else:
        n += 1
        insert(A, int(s[7:]))



# Optimized solution
import sys
readline = sys.stdin.readline
def maxHeapify(A, i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < n and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r < n and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        maxHeapify(A, largest)
def insert(S, k):
    S.append(k)
    i = n - 1
    p = (i - 1) // 2
    while i > 0 and S[i] > S[p]:
        S[i], S[p] = S[p], S[i]
        i = p
        p = (i - 1) // 2
def extractMax(S):
    if len(S) == 1:
        return S.pop()
    ans = S[0]
    S[0] = S.pop()
    maxHeapify(S, 0)
    return ans
A = []
n = 0
while True:
    s = readline()
    if s[2] == "d":
        break
    elif s[2] == "t":
        n -= 1
        print((extractMax(A)))
    else:
        n += 1
        insert(A, int(s[7:]))
# Original solution
import sys
readline = sys.stdin.readline
def maxHeapify(A, i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < n:
        largest = l
        if r < n and A[r] > A[l]:
            largest = r
        if A[largest] > A[i]:
            A[i], A[largest] = A[largest], A[i]
            maxHeapify(A, largest)
def insert(S, k):
    global n
    S[n] = k
    n += 1
    i = n - 1
    p = (i - 1) // 2
    while i > 0 and S[i] > S[p]:
        S[i], S[p] = S[p], S[i]
        i = p
        p = (i - 1) // 2
def extractMax(S):
    global n
    if n == 1:
        n -= 1
        return S[0]
    ans = S[0]
    n -= 1
    S[0] = S[n]
    maxHeapify(S, 0)
    return ans
A = [0] * 2000000
n = 0
for s in sys.stdin:
    if s[2] == "s":
        insert(A, int(s[7:]))
    elif s[2] == "t":
        print((extractMax(A)))
    else:
        break



# Optimized solution
import sys
readline = sys.stdin.readline
def maxHeapify(A, i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < n:
        largest = l
        if r < n and A[r] > A[l]:
            largest = r
        if A[largest] > A[i]:
            A[i], A[largest] = A[largest], A[i]
            maxHeapify(A, largest)
def insert(S, k):
    global n
    S[n] = k
    n += 1
    i = n - 1
    p = (i - 1) // 2
    while i > 0 and S[i] > S[p]:
        S[i], S[p] = S[p], S[i]
        i = p
        p = (i - 1) // 2
def extractMax(S):
    global n
    if n == 1:
        n -= 1
        return S[0]
    ans = S[0]
    n -= 1
    S[0] = S[n]
    i = 0
    while True:
        l = i * 2 + 1
        r = i * 2 + 2
        if l >= n:
            break
        largest = l
        if r < n and A[r] > A[l]:
            largest = r
        if A[largest] > A[i]:
            A[i], A[largest] = A[largest], A[i]
            i = largest
        else:
            break
    return ans
A = [0] * 2000000
n = 0
for s in sys.stdin:
    if s[2] == "s":
        insert(A, int(s[7:]))
    elif s[2] == "t":
        print((extractMax(A)))
    else:
        break
# Original solution
import sys
def maxHeapify(A, i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < n:
        largest = l
        if r < n and A[r] > A[l]:
            largest = r
        if A[largest] > A[i]:
            A[i], A[largest] = A[largest], A[i]
            maxHeapify(A, largest)
def insert(S, k):
    global n
    S[n] = k
    n += 1
    i = n - 1
    p = (i - 1) // 2
    while i > 0 and S[i] > S[p]:
        S[i], S[p] = S[p], S[i]
        i = p
        p = (i - 1) // 2
def extractMax(S):
    global n
    if n == 1:
        n -= 1
        return S[0]
    ans = S[0]
    n -= 1
    S[0] = S[n]
    i = 0
    while True:
        l = i * 2 + 1
        r = i * 2 + 2
        if l >= n:
            break
        largest = l
        if r < n and A[r] > A[l]:
            largest = r
        if A[largest] > A[i]:
            A[i], A[largest] = A[largest], A[i]
            i = largest
        else:
            break
    return ans
A = [0] * 2000000
S = []
n = 0
for s in sys.stdin:
    if s[2] == "s":
        insert(A, int(s[7:]))
    elif s[2] == "t":
        S.append(extractMax(A))
    else:
        break
print(("\n".join(map(str, S))))



# Optimized solution
import sys
from heapq import heapify, heappush, heappop
hq = []
S = []
for s in sys.stdin:
    if s[2] == "s":
        heappush(hq, -int(s[7:]))
    elif s[2] == "t":
        S.append(-heappop(hq))
    else:
        break
print(("\n".join(map(str, S))))