import sys
n=int(sys.stdin.readline().strip())
l=[]
for _ in range(n):
    line=sys.stdin.readline().split()
    op=line[0]
    if op=='1':
        x=int(line[1])
        l.append(x)
        l.sort()
    elif op=='2':
        print(l[0])
    elif op=='3':
        print(l[-1])
    elif op=='4':
        l.pop(0)
    else:
        l.pop(-1)