カスタムヒープの実装
最初は空のヒープが与えられており、q
個のクエリを実行する必要があります。クエリには以下の 3 種類があります:
add x
- ヒープにx
を追加しますpop
- ヒープのルート要素を削除しますmax
- ヒープの最大要素を出力します
入力
最初の行には、整数 q
(1 ≤ q
≤ 10^5) が 1 つ与えられます。
続く q
行には、各行に 1 つずつクエリが記述されます。すべての add
クエリにおける x
の絶対値は を超えないことが保証されています。また、すべての操作が有効であり、空のヒープに対して pop
を呼び出すことはありません。
出力
プログラムは、すべての max
クエリに対して求められる値を、それぞれ別の行に出力してください。
例
入力 | 出力 |
---|---|
9 add 1 add 2 max add -3 add 4 max add -2 pop max | 2 4 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB