Heaps - Priority Queue

Time Limit : 2 sec, Memory Limit : 131072 KB

優先順位キュー

優先度付きキュー (priority queue) は各要素がキーを持ったデータの集合 $S$ を保持するデータ構造で、主に次の操作を行います:

  • $insert(S, k)$: 集合 $S$ に要素 $k$ を挿入する
  • $extractMax(S)$: 最大のキーを持つ $S$ の要素を $S$ から削除してその値を返す

優先度付きキュー $S$ に対して $insert(S, k)$、$extractMax(S)$を行うプログラムを作成してください。ここでは、キューの要素を整数とし、それ自身をキーとみなします。

入力

優先度付きキュー $S$ への複数の命令が与えられます。各命令は、insert $k$、extractまたはendの形式で命令が1行に与えられます。ここで $k$ は挿入する整数を表します。

end命令が入力の終わりを示します。

出力

extract命令ごとに、優先度付きキュー $S$から取り出される値を1行に出力してください。

制約

  • 命令の数は$2,000,000$を超えない。
  • $0 \leq $k$ \leq 2,000,000,000$

入力例 1

insert 8
insert 2
extract
insert 10
extract
insert 11
extract
extract
end

出力例 1

8
10
11
2

Note

      解説