← 返回题目列表

Codeforces · 1468/C

C. 贝尔比萨

中文机器翻译题面 查看原题

Monocarp 和 Polycarp 在 Berpizza 做服务员,这是一家位于 Bertown 中心附近的披萨店。既然他们是服务员,他们的工作就是为顾客服务,但他们选择先服务的对象的方式不同。

工作日开始时,Berpizza 没有顾客。他们一一来到那里。当顾客走进比萨店时,她会坐下来等待 Monocarp 或 Polycarp 为她服务。 Monocarp 在 Berpizza 工作了短短两周,所以每当他为顾客服务时,他只是选择第一个来到 Berpizza 的顾客,并为该顾客提供服务。

另一方面,Polycarp 是 Berpizza 的一位经验丰富的服务员,他一看到顾客就知道哪些顾客会在比萨店花很多钱(哪些不会)。对于每个顾客,Polycarp 都会估算该顾客可以花的金额,当他为顾客服务时,他会选择预计在 Berpizza 留下最多钱的顾客(如果有多个这样的顾客,他会选择其中排在第一位的顾客)。

显然,任何客户都不能被服务两次,因此 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$$$) — 一位顾客来到 Berpizza,Polycarp 估计他们将花费的金额为 $$$m$$$;
- $$$2$$$ — Monocarp 为先到披萨店的顾客提供服务;
- $$$3$$$ — Polycarp 为一位预计在比萨店消费最多的顾客提供服务(如果有多个这样的顾客,则选择第一个来到比萨店的顾客)。

仅当存在至少一名尚未得到服务的客户时,才会询问 $$$2$$$ 和 $$$3$$$ 类型的查询。输入中至少有一个 $$$2$$$ 或 $$$3$$$ 类型的查询。

输出

对于 $$$2$$$ 或 $$$3$$$ 类型的每个查询,打印一个整数 — 在该事件中已服务的客户数量。顾客按照来到比萨店的顺序编号,从 $$$1$$$ 开始。

示例

输入 #1

8
1 8
1 10
1 6
3
2
1 9
2
3

输出 #1

2 1 3 4

输入 #2

6
1 8
1 10
1 8
3
3
3

输出 #2

2 1 3

输入 #3

8
1 103913
3
1 103913
1 103913
3
1 103913
1 103913
2

输出 #3

1 2 3