CF1468C Berpizza

Monocarp 和 Polycarp 是 Berpizza 比萨店的服务员。作为服务员，他们的工作是为顾客服务，但他们选择服务对象的方式不同。 一天开始时，Berpizza 没有顾客。顾客会一个接一个地到来。每当有顾客进入比萨店时，她会坐下等待 Monocarp 或 Polycarp 为她服务。Monocarp 在 Berpizza 工作仅两周，所以每次他服务顾客时，总是选择最早到达的那位顾客。 而 Polycarp 是 Berpizza 的资深服务员，他一眼就能判断每位顾客在比萨店可能花费多少钱。对于每位顾客，Polycarp 都会估算她的消费金额。当他服务顾客时，总是选择预计花费最多的那位（如果有多位预计花费相同，则选择其中最早到达的那位）。 显然，每位顾客只能被服务一次，因此 Monocarp 和 Polycarp 只能在尚未被服务的顾客中选择。 当顾客数量变得非常多时，Monocarp 和 Polycarp 都很难手动选择要服务的顾客。你的任务是编写一个程序，帮助他们做出选择。具体来说，你需要处理三种类型的操作： - $1\ m$ —— 有一位顾客来到 Berpizza，Polycarp 估算她的消费金额为 $m$； - $2$ —— Monocarp 服务最早到达的那位尚未被服务的顾客； - $3$ —— Polycarp 服务预计花费最多的那位尚未被服务的顾客（如果有多位预计花费相同，则选择其中最早到达的那位）。 对于每个类型为 $2$ 和 $3$ 的操作，输出被服务顾客的编号（顾客按到达顺序编号，从 $1$ 开始）。

第一行包含一个整数 $q$（$2 \le q \le 5 \cdot 10^5$）——操作的数量。 接下来 $q$ 行，每行描述一个操作，格式如下： - $1\ m$（$1 \le m \le 5 \cdot 10^5$）——有一位顾客到来，Polycarp 估算她的消费金额为 $m$； - $2$ —— Monocarp 服务最早到达的那位尚未被服务的顾客； - $3$ —— Polycarp 服务预计花费最多的那位尚未被服务的顾客（如果有多位预计花费相同，则选择其中最早到达的那位）。 仅当存在至少一位尚未被服务的顾客时，才会出现类型为 $2$ 或 $3$ 的操作。输入中至少有一个类型为 $2$ 或 $3$ 的操作。

对于每个类型为 $2$ 或 $3$ 的操作，输出一个整数——本次被服务顾客的编号。顾客按到达顺序编号，从 $1$ 开始。

由 ChatGPT 4.1 翻译