AtCoder Beginner Contest 217 [ E - Sorting Queries ] https://atcoder.jp/contests/abc217/tasks/abc217_e

abc217_e.py

'''
[問題]
https://atcoder.jp/contests/abc217/tasks/abc217_e

[参考]
https://atcoder.jp/contests/abc217/editorial/2577
　公式解説のロジックをPythonにコンバート

PythonのQueueモジュールの使い方【初心者向け】
https://techacademy.jp/magazine/18995
'''

import sys
import queue
import heapq

sys.setrecursionlimit(10 ** 6)  # 再帰上限の引き上げ
input = sys.stdin.readline

INF = 2 ** 63 - 1

Q1 = queue.Queue()
Q2 = []     # heapq用

Q = int(input())

for _ in range(Q):

    q = list(map(int, input().split()))
    if q[0] == 1:
        # q[1]が仮に最小値だったとしてもソートが呼ばれるまでは先頭にいかないので、Q1に入れとくで問題無い
        Q1.put(q[1])
    elif q[0] == 2:
        if len(Q2) == 0:
            # Q2が空ならばソート前
            print(Q1.get())
        else:
            # 優先度付きキューは常に最小値を返す（ソート済みと同じ）
            print(heapq.heappop(Q2))
    else:
        # ソートが呼ばれたらQ1の中身をQ2へ移す
        while not Q1.empty():
            heapq.heappush(Q2, Q1.get())