CodeEff/ECCO huggingface dataset:
# Original solution
from itertools import accumulate
n, *A = list(map(int, open(0).read().split()))
if A[0] != 0:
    if A[0] == 1 and n == 0:
        print((1))
    else:
        print((-1))
else:
    B = list(accumulate(A[::-1]))[::-1] + [0]
    C = [0] * (n+1)
    D = [0] * (n+1)
    C[0] = 1
    D[0] = 1

    for i in range(1, n+1):
        C[i] = min(B[i], 2*D[i-1])
        D[i] = C[i] - A[i]
        if D[i] < 0:
            print((-1))
            break
    else:
        print((sum(C)))

# Optimized solution
from itertools import accumulate
n, *A = list(map(int, open(0).read().split()))
if A[0] != 0:
    if A[0] == 1 and n == 0:
        print((1))
    else:
        print((-1))
else:
    B = list(accumulate(A[::-1]))[::-1]
    C = [1] * (n+1)
    D = [1] * (n+1)

    for i in range(1, n+1):
        C[i] = min(B[i], 2*D[i-1])
        D[i] = C[i] - A[i]
        if D[i] < 0:
            print((-1))
            break
    else:
        print((sum(C)))
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
b = a[::-1]

if n == 0 and a[0] == 1:
    print((1))
    exit()

if n == 0:
    print((-1))
    exit()
      
if a[0] >= 1:
    print((-1))
    exit()
    
ans = [0] * (n + 1)
for i in range(n):
    ans[i + 1] = ans[i] + b[i]

ans = ans[::-1]

ans = ans[1::]
a = a[1::]

res = 1
prev_cnt = 1

for i in range(n):
    cnt = min(prev_cnt * 2, ans[i] + a[i])
    if cnt < a[i]:
        print((-1))
        exit()
    res += cnt
    prev_cnt = cnt - a[i]
print(res)


# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
b = a[::-1]

if n == 0 and a[0] == 1:
    print((1))
    exit()

if a[0] >= 1:
    print((-1))
    exit()
    
ans = [0] * (n + 1)
for i in range(n):
    ans[i + 1] = ans[i] + b[i]

ans = ans[::-1]

ans = ans[1::]
a = a[1::]

res = 1
prev_cnt = 1

for i in range(n):
    cnt = min(prev_cnt * 2, ans[i] + a[i])
    if cnt < a[i]:
        print((-1))
        exit()
    res += cnt
    prev_cnt = cnt - a[i]
print(res)
# Original solution

def resolve():
  N = int(eval(input()))
  A = [int(x) for x in input().split(" ")]
  if N == 0 and A[0] != 1:
    print((-1))
    return True
  min_maxs = {}
  min_maxs[len(A)-1] = [A[-1], A[-1]]

  for index in reversed(list(range(len(A)-1))):
    min_maxs[index] = [min_maxs[index+1][0] // 2 + A[index], min_maxs[index+1][1] + A[index]]
  # print(min_maxs)
    # min_maxs.insert(0, [min_maxs[0][0] // 2 + a, min_maxs[0][1] + a])
  # print(min_maxs)
  # max_node_in_depth = [sum(A[i:]) for i in range(len(A))]

  # # 各 depth における最小値
  # min_node_in_depth = [0] * (len(A))
  # min_node_in_depth[-1] = max_node_in_depth[-1]
  # index = -1
  # for i in range(1, len(A)):
  #   min_node_in_depth[index] = -(-min_node_in_depth[index + 1] // 2) + A[index]
  #   index = index - 1

  # for min_max in min_maxs:
  #   print(min_max)

  result = 1
  recent = 1
  for index in range(1, len(A)):
    num_of_node = (recent - A[index-1]) * 2
    # print(min_max, num_of_node)
    if num_of_node < min_maxs[index][0]:
      print((-1))
      return True
    
    result += min(num_of_node, min_maxs[index][1])
    recent = min(num_of_node, min_maxs[index][1])

  print(result)

if __name__ == "__main__":
    resolve()

# Optimized solution
def resolve():
  N = int(eval(input()))
  A = [int(x) for x in input().split(" ")]
  if N == 0 and A[0] != 1:
    print((-1))
    return True
  min_maxs = [0] * len(A)
  min_maxs[len(A)-1] = [A[-1], A[-1]]

  for index in reversed(list(range(len(A)-1))):
    min_maxs[index] = [min_maxs[index+1][0] // 2 + A[index], min_maxs[index+1][1] + A[index]]

  result = 1
  recent = 1
  for index in range(1, len(A)):
    num_of_node = (recent - A[index-1]) * 2
    if num_of_node < min_maxs[index][0]:
      print((-1))
      return True
    
    result += min(num_of_node, min_maxs[index][1])
    recent = min(num_of_node, min_maxs[index][1])

  print(result)

if __name__ == "__main__":
    resolve()
# Original solution
from itertools import accumulate
n=int(eval(input()))
a=list(map(int,input().split()))
c=list(accumulate(a))
b=[0]*(n+1)
#大きくしすぎてしまう場合がある
#いや上限を考えろや
def f():
    global n,a,b
    for i in range(n+1):
        if i==0:
            b[0]=min(c[n]-c[0],1)
        else:
            b[i]=min(2*(b[i-1]-a[i-1]),c[n]-c[i-1])

    if n==0:
        if a[0]!=1:
            print((-1))
        else:
            print((1))
    elif b[n]!=a[n]:
        print((-1))
    else:
        print((sum(b)))
        #print(b)
f()

# Optimized solution
n,*a=list(map(int,open(0).read().split()))
t,v=sum(a),[1]
for q in a:
    v+=[min(2*(v[-1]-q),t:=t-q)]
    if v[-1]<0:print((-1));exit()
print((sum(v)))
# Original solution
n,*a=list(map(int,open(0).read().split()))
t,v,w=sum(a),1,1
for q in a:
  w=min(2*(w-q),t:=t-q);(v:=v+w)
  if w<0:print((-1));exit()
print(v)

# Optimized solution
n,*a=list(map(int,open(0).read().split()))
t=sum(a);v=w=1
for q in a:
  w=min(2*(w-q),t:=t-q);(v:=v+w)
  if w<0:print((-1));exit()
print(v)
# Original solution
n,*a=list(map(int,open(0).read().split()))
t=sum(a);v=w=1
for q in a:
  w=min(2*(w-q),t:=t-q);(v:=v+w)
  if w<0:print((-1));exit()
print(v)

# Optimized solution
n,*a=list(map(int,open(0).read().split()))
t=sum(a);v=w=1
for q in a:
  if(w:=min(2*(w-q),t:=t-q))<0:print((-1));exit()
  v+=w
print(v)
# Original solution
n,*a=map(int,open(0).read().split());t=sum(a);v=w=1
for q in a:
  if(w:=min(2*(w-q),t:=t-q))<0:exit(print(-1))
  v+=w
print(v)


# Optimized solution
n,*a=map(int,open(0).read().split());t=sum(a);v=w=1
print(sum([1]+[exit(print(-1)) if(w:=min(2*(w-q),t:=t-q))<0 else w for q in a]))
# Original solution
p=print;n,*a=map(int,open(0).read().split());t=sum(a);p(sum([w:=1]+[exit(p(-1))if(w:=min(2*(w-q),t:=t-q))<0 else w for q in a]))


# Optimized solution
p,s=print,sum;n,*a=map(int,open(0).read().split());t=s(a);p(s([w:=1]+[exit(p(-1))if(w:=min(2*(w-q),t:=t-q))<0 else w for q in a]))
# Original solution
W, H, x, y= list(map(int, input().split()))
S = W*H/2
flg = 1 if (x==W/2 and y==H/2) else 0
print(('{:.6f}'.format(S)+" "+str(flg)))

# Optimized solution
W, H, x, y= list(map(int, input().split()))
print(('{:.6f}'.format(W*H/2)+" "+str(1 if (x==W/2 and y==H/2) else 0)))
# Original solution
# AOJ ITP2_3_C: Count
# Python3 2018.6.24 bal4u

n = int(eval(input()))
a = list(map(int, input().split()))
q = int(eval(input()))
for i in range(q):
	b, e, k = list(map(int, input().split()))
	s = a[b:e]
	print((s.count(k)))


# Optimized solution
# AOJ ITP2_3_C: Count
# Python3 2018.6.24 bal4u

n = int(eval(input()))
a = list(map(int, input().split()))
q = int(eval(input()))
for i in range(q):
	b, e, k = list(map(int, input().split()))
	print((a[b:e].count(k)))
# Original solution
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


def max_heapify(index):
    # global heap_length
    left, right, largest = 2 * index, 2 * index + 1, None

    if left <= heap_length and heap_array[left] > heap_array[index]:
        largest = left
    else:
        largest = index

    if right <= heap_length and heap_array[right] > heap_array[largest]:
        largest = right

    if largest != index:
        heap_array[index], heap_array[largest] = heap_array[largest], heap_array[index]
        max_heapify(largest)

    return None


def extract():
    global heap_length
    if heap_length < 1:
        raise SystemExit('Heap underflow!')
    # the root of the heap is always the largest
    heap_max = heap_array[1]

    # move new data to heap root
    heap_array[1] = heap_array[heap_length]
    heap_length -= 1

    # print
    heap_array.pop()
    print(heap_max)
    max_heapify(1)
    # assert len(heap_array) == heap_length + 1
    return heap_max


def insert(data):
    global heap_length
    heap_length += 1
    heap_array.append(-1)
    # assert len(heap_array) == heap_length + 1
    insert_data(heap_length, data)


def insert_data(index, data):
    if data < heap_array[index]:
        raise SystemExit('Not a max-heap!')
    heap_array[index] = data
    while index > 1:
        parent = index // 2
        if heap_array[parent] >= heap_array[index]:
            break
        heap_array[index], heap_array[parent] = heap_array[parent], heap_array[index]
        index //= 2
    return None


def action(_command):
    if _command.startswith('in'):
        insert(int(each[7:]))
    elif _command.startswith('ex'):
        extract()

    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    # command_list = list(map(lambda x: x.split(), _input))

    # allowed_commands = ('insert', 'extract', 'end')
    heap_array, heap_length = [-1], 0
    for each in _input:
        # command, content = each[0], each[-1]
        # if command not in allowed_commands:
        #     raise SystemExit('Illegal command!')

        action(each)

# Optimized solution
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
import heapq as hp

if __name__ == '__main__':
    _input = sys.stdin.readlines()

    heap_array = []
    for each in _input:
        if each.startswith('in'):
            hp.heappush(heap_array, -1 * int(each[7:]))
        elif each.startswith('ex'):
            print((-1 * hp.heappop(heap_array)))
# Original solution
import sys

#@profile
def max_heapify(A, i):
    j = i
    largest = i
    H = len(A) -1
    while True:
        l = j * 2
        r = l + 1
        if l <= H and A[l] > A[j]:
            largest = l
        if r <= H and A[r] > A[largest]:
            largest = r
        if largest != j:
            A[j], A[largest] = A[largest], A[j]
            #max_heapify(A, largest)
            j = largest
            
        else:
            break
        

#@profile
def build_max_heap(A):
    for i in range(len(A)-1 // 2, 0, -1):
        max_heapify(A, i)

#@profile
def extract(A):
    print(A[1])
    A[1] = A[-1]
    del A[-1]
    max_heapify(A, 1)
    
A = [0]

#@profile
def main():
    out = ""
    for l in sys.stdin.readlines():
        if l[0] == "i":
            #insert k
            A.append(int(l[7:]))
            build_max_heap(A)
        #print(A)
        elif l[1] == "n":
            #end
            print(out, end = "")
            return
        else:
            if len(A) <= 1:
                pass
            elif len(A) == 2:
                out += str(A.pop()) + "\n"
                #print(A.pop())
            #extract(A)
            else:
                out += str(A[1]) + "\n"
                A[1] = A.pop()
                max_heapify(A, 1)
                
if __name__ == "__main__":
    main()


# Optimized solution
import sys

#@profile
def max_heapify(A, i):
    j = i
    largest = i
    H = len(A) -1
    while True:
        l = j * 2
        r = l + 1
        if l <= H and A[l] > A[j]:
            largest = l
        if r <= H and A[r] > A[largest]:
            largest = r
        if largest != j:
            A[j], A[largest] = A[largest], A[j]
            #max_heapify(A, largest)
            j = largest
            
        else:
            break
        

#@profile
def build_max_heap(A):
    i = len(A)-1
    last = A[i]
    parent = i//2
    while  parent > 0 and A[parent] < last:
        A[i] = A[parent]
        i = parent
        parent = i //2
    A[i] = last

#@profile
def extract(A):
    print(A[1])
    A[1] = A[-1]
    del A[-1]
    max_heapify(A, 1)
    
A = [0]

#@profile
def main():
    out = ""
    for l in sys.stdin.readlines():
        if l[0] == "i":
            #insert k
            A.append(int(l[7:]))
            build_max_heap(A)
        #print(A)
        elif l[1] == "n":
            #end
            print(out, end = "")
            return
        else:
            if len(A) <= 1:
                pass
            elif len(A) == 2:
                out += str(A.pop()) + "\n"
                #print(A.pop())
            #extract(A)
            else:
                out += str(A[1]) + "\n"
                A[1] = A.pop()
                max_heapify(A, 1)
                
if __name__ == "__main__":
    main()
# Original solution
class PQueue:
    def __init__(self):
        self.keys = []
        
    def maxHeapify(self, i):
        l = i * 2 + 1
        r = i * 2 + 2
        if l < len(self.keys) and self.keys[l] > self.keys[i]:
            largest = l
        else:
            largest = i
        if r < len(self.keys) and self.keys[r] > self.keys[largest]:
            largest = r
        if largest != i:
            self.keys[i], self.keys[largest] = self.keys[largest], self.keys[i]
            self.maxHeapify(largest)

    def insert(self, key):
        i = len(self.keys)
        self.keys.append(key)
        parent = (i - 1) // 2
        while i > 0 and self.keys[parent] < self.keys[i]:
            self.keys[i], self.keys[parent] = self.keys[parent], self.keys[i]
            i = parent
            parent = (parent - 1) // 2

    def heapExtraMax(self):
        max_key = self.keys[0]
        if len(self.keys) > 1:
            self.keys[0] = self.keys.pop()
        else:
            del self.keys[0]
        self.maxHeapify(0)
        print(max_key)


S = PQueue()
ans = []

import sys

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        S.insert(k)
    elif x[1] == 'x':
        S.heapExtraMax()
    else:
        pass

# Optimized solution
class PQueue:
    def __init__(self):
        self.keys = []
        
    def maxHeapify(self, i):
        l = i * 2 + 1
        r = i * 2 + 2
        if l < len(self.keys) and self.keys[l] > self.keys[i]:
            largest = l
        else:
            largest = i
        if r < len(self.keys) and self.keys[r] > self.keys[largest]:
            largest = r
        if largest != i:
            self.keys[i], self.keys[largest] = self.keys[largest], self.keys[i]
            self.maxHeapify(largest)

    def insert(self, key):
        i = len(self.keys)
        self.keys.append(key)
        parent = (i - 1) // 2
        while i > 0 and self.keys[parent] < self.keys[i]:
            self.keys[i], self.keys[parent] = self.keys[parent], self.keys[i]
            i = parent
            parent = (parent - 1) // 2

    def heapExtraMax(self):
        max_key = self.keys[0]
        if len(self.keys) > 1:
            self.keys[0] = self.keys.pop()
        else:
            del self.keys[0]
        self.maxHeapify(0)
        return max_key


S = PQueue()
ans = []

import sys

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        S.insert(k)
    elif x[1] == 'x':
        ans.append(S.heapExtraMax())
    else:
        pass

print(*ans, sep = '\n')
# Original solution
class PQueue:
    def __init__(self):
        self.keys = []
        
    def maxHeapify(self, i):
        l = i * 2 + 1
        r = i * 2 + 2
        if l < len(self.keys) and self.keys[l] > self.keys[i]:
            largest = l
        else:
            largest = i
        if r < len(self.keys) and self.keys[r] > self.keys[largest]:
            largest = r
        if largest != i:
            self.keys[i], self.keys[largest] = self.keys[largest], self.keys[i]
            self.maxHeapify(largest)

    def insert(self, key):
        i = len(self.keys)
        self.keys.append(key)
        parent = (i - 1) // 2
        while i > 0 and self.keys[parent] < self.keys[i]:
            self.keys[i], self.keys[parent] = self.keys[parent], self.keys[i]
            i = parent
            parent = (parent - 1) // 2

    def heapExtraMax(self):
        max_key = self.keys[0]
        if len(self.keys) > 1:
            self.keys[0] = self.keys.pop()
        else:
            del self.keys[0]
        self.maxHeapify(0)
        return max_key


S = PQueue()
ans = []

import sys

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        S.insert(k)
    elif x[1] == 'x':
        ans.append(S.heapExtraMax())
    else:
        pass

print(*ans, sep = '\n')


# Optimized solution
def maxHeapify(keys, i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < len(keys) and keys[l] > keys[i]:
        largest = l
    else:
        largest = i
    if r < len(keys) and keys[r] > keys[largest]:
        largest = r
    if largest != i:
        keys[i], keys[largest] = keys[largest], keys[i]
        maxHeapify(keys, largest)

def heapInsert(keys, key):
    i = len(keys)
    keys.append(key)
    parent = (i - 1) // 2
    while i > 0 and keys[parent] < keys[i]:
        keys[i], keys[parent] = keys[parent], keys[i]
        i = parent
        parent = (parent - 1) // 2

def heapMaxPop(keys):
    max_key = keys[0]
    if len(keys) > 1:
        keys[0] = keys.pop()
    else:
        del keys[0]
    maxHeapify(keys, 0)
    print(max_key)


S = []

import sys

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        heapInsert(S, k)
    elif x[1] == 'x':
        heapMaxPop(S)
    else:
        pass
# Original solution
def maxHeapify(i):
    l = i * 2 + 1
    r = i * 2 + 2
    if l < len(A) and A[l] > A[i]:
        largest = l
    else:
        largest = i
    if r < len(A) and A[r] > A[largest]:
        largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        maxHeapify(largest)

def heapInsert(key):
    i = len(A)
    A.append(key)
    parent = (i - 1) // 2
    while i > 0 and A[parent] < A[i]:
        A[i], A[parent] = A[parent], A[i]
        i = parent
        parent = (parent - 1) // 2

def heapMaxPop():
    max_key = A[0]
    if len(A) > 1:
        A[0] = A.pop()
    else:
        del A[0]
    maxHeapify(0)
    print(max_key)


A = []

import sys

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        heapInsert(k)
    elif x[1] == 'x':
        heapMaxPop()
    else:
        pass

# Optimized solution
def setHeapDown_max(heap, pos):
    targetkey = heap[pos]
    while pos > 0:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if parent < targetkey:
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = targetkey

def setHeapUp_max(heap, pos):
    endpos = len(heap)
    targetkey = heap[pos]
    childpos = 2*pos + 1
    while childpos < endpos:
        rightpos = childpos + 1
        if rightpos < endpos and not heap[rightpos] < heap[childpos]:
            childpos = rightpos
        heap[pos] = heap[childpos]
        pos = childpos
        childpos = 2*pos + 1
    heap[pos] = targetkey
    setHeapDown_max(heap, pos)

def heapPush_max(heap, key):
    heap.append(key)
    setHeapDown_max(heap, len(heap) - 1)

def heapPop_max(heap):
    lastkey = heap.pop()
    if heap:
        returnkey = heap[0]
        heap[0] = lastkey
        setHeapUp_max(heap, 0)
        return returnkey
    return lastkey


import sys

S = []

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        heapPush_max(S, k)
    elif x[1] == 'x':
        print((heapPop_max(S)))
    else:
        pass
# Original solution
def setHeapDown_max(heap, pos):
    targetkey = heap[pos]
    while pos > 0:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if parent < targetkey:
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = targetkey

def setHeapUp_max(heap, pos):
    endpos = len(heap)
    targetkey = heap[pos]
    childpos = 2*pos + 1
    while childpos < endpos:
        rightpos = childpos + 1
        if rightpos < endpos and not heap[rightpos] < heap[childpos]:
            childpos = rightpos
        childkey = heap[childpos]
        if targetkey > childkey:
            break
        heap[pos] = childkey
        pos = childpos
        childpos = 2*pos + 1
    heap[pos] = targetkey

def heapPush_max(heap, key):
    heap.append(key)
    setHeapDown_max(heap, len(heap) - 1)

def heapPop_max(heap):
    lastkey = heap.pop()
    if heap:
        returnkey = heap[0]
        heap[0] = lastkey
        setHeapUp_max(heap, 0)
        return returnkey
    return lastkey


import sys

S = []

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        heapPush_max(S, k)
    elif x[1] == 'x':
        print((heapPop_max(S)))
    else:
        pass

# Optimized solution
def setHeapDown_max(heap, pos):
    targetkey = heap[pos]
    while pos > 0:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if parent < targetkey:
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = targetkey

def setHeapUp_max(heap, pos):
    endpos = len(heap)
    targetkey = heap[pos]
    childpos = 2*pos + 1
    while childpos < endpos:
        rightpos = childpos + 1
        if rightpos < endpos and not heap[rightpos] < heap[childpos]:
            childpos = rightpos
        childkey = heap[childpos]
        if targetkey > childkey:
            break
        heap[pos] = childkey
        pos = childpos
        childpos = 2*pos + 1
    heap[pos] = targetkey

def heapPush_max(heap, key):
    heap.append(key)
    setHeapDown_max(heap, len(heap) - 1)

def heapPop_max(heap):
    lastkey = heap.pop()
    if heap:
        returnkey = heap[0]
        heap[0] = lastkey
        setHeapUp_max(heap, 0)
        return returnkey
    return lastkey


import sys

S = []

ans = []

for x in sys.stdin.readlines():
    if x[0] == 'i':
        k = int(x[7:])
        heapPush_max(S, k)
    elif x[1] == 'x':
        ans.append(heapPop_max(S))
    else:
        pass

print(*ans, sep = '\n')
# Original solution
import sys

def max_heapify(A, i):
  H = len(A) - 1
  l, r, m = i*2, i*2+1, i
  if l <= H and A[l] > A[i]: m = l
  if r <= H and A[r] > A[m]: m = r

  if m != i:
    A[i], A[m] = A[m], A[i]
    max_heapify(A, m)

def build_max_heap(A):
  H = len(A) - 1
  for i in range(H // 2, 0, -1):
    max_heapify(A, i)

A = [0]

for line in sys.stdin.readlines():
  if line[0] == 'i':
    A.append(int(line[7:]))
    build_max_heap(A)
  elif line[1] == 'x':
    if len(A) <= 2:
      print((A.pop()))
    else:
      print((A[1]))
      A[1] = A.pop()
      max_heapify(A, 1)
  else:
    exit()

# Optimized solution
import sys

def max_heapify(A, H, i):
  target = A[i]

  m = i
  l = i * 2
  while l <= H:
    largest = target
    if A[l] > target:
      m = l
      largest = A[m]

    r = l + 1
    if r <= H and A[r] > largest:
      m = r
      largest = A[m]

    if m != i:
      A[i] = largest
      i = m
      l = i * 2
    else:
      break

  A[m] = target

def build_max_heap(A, i):
  if i < 2: return
  last = A[i]
  p = i // 2
  while p > 0 and A[p] < last:
    A[i] = A[p]
    i = p
    p = i // 2
  A[i] = last

A = [0]

for line in sys.stdin.readlines():
  if line[0] == 'i':
    A.append(int(line[7:]))
    build_max_heap(A, len(A) - 1)
  elif line[1] == 'x':
    if len(A) <= 1:
      pass
    elif len(A) <= 2:
      print((A.pop()))
    else:
      print((A[1]))
      A[1] = A.pop()
      max_heapify(A, len(A) -1, 1)
  else:
    exit()
# Original solution
import sys
def h(i):
 l=2*i;r=l+1
 if r<=H:
  if A[i]<A[l]:
   if A[l]<A[r]:A[i],A[r]=A[r],A[i];h(r)
   else:A[i],A[l]=A[l],A[i];h(l)
  elif A[i]<A[r]:A[i],A[r]=A[r],A[i];h(r)
 elif l<=H and A[i]<A[l]:A[i],A[l]=A[l],A[i];h(l)
H=0
A=[0]*2000001
o=''
for e in sys.stdin:
 if'i'==e[0]:
  H+=1;A[H]=int(e[7:]);k=H
  while k>1 and A[k//2]<A[k]:A[k],A[k//2]=A[k//2],A[k];k//=2
 elif'x'==e[1]:
  o+=f'{A[1]}\n';H-=1
  if H:A[1]=A[H+1];h(1)
print((o[:-1]))


# Optimized solution
import sys
from heapq import *
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
print(("\n".join(map(str,O))))
# Original solution
import sys
from heapq import *
H=[]
O=''
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif'x'==e[1]:O+=f'{-heappop(H)}\n'
print((O[:-1]))


# Optimized solution
import sys
from heapq import *
H,O=[],[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif'x'==e[1]:O+=[-heappop(H)]
print(('\n'.join(map(str,O))))
# Original solution
import sys
from heapq import *
H=[]
O=[]
for e in sys.stdin:
 if'end'==e:break
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
print(('\n'.join(map(str,O))))


# Optimized solution
import sys
from heapq import *
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
 else:print(('\n'.join(map(str,O))))