双端优先队列

【题目描述】

给定一个多重集合 $S=\lbrace S_1, \ldots, S_N \rbrace$。按顺序处理以下 $Q$ 个查询：

• 0 x：将 $x$ 加入 $S$。
• 1：输出 $S$ 中的一个最小元素，并将其从 $S$ 中删除。
• 2：输出 $S$ 中的一个最大元素，并将其从 $S$ 中删除。

保证处理类型为 1 和 2 的查询时，$S$ 非空。

【输入】

$N\; Q$
$S_1 \cdots S_N$
$\mathrm{Query}_0$
$\vdots$
$\mathrm{Query}_{Q-1}$

【输出】

对于每个类型为 1 或 2 的查询，输出一行一个整数。

【输入样例】

4 10
-3 0 1 3
0 3
2
2
0 -2
0 1
1
1
2
1
2

【输出样例】

3
3
-3
-2
1
0
1

【数据范围】

• $0 \leq N \leq 500000$
• $1 \leq Q \leq 500000$
• $-1000000000 \leq S _i, x \leq 1000000000$

【来源】

Library Checker（yosupo06） double_ended_priority_queue