CF1468C.Berpizza

Monocarp and Polycarp are working as waiters in Berpizza, a pizzeria located near the center of Bertown. Since they are waiters, their job is to serve the customers, but they choose whom they serve first differently.

At the start of the working day, there are no customers at the Berpizza. They come there one by one. When a customer comes into the pizzeria, she sits and waits for Monocarp or Polycarp to serve her. Monocarp has been working in Berpizza for just two weeks, so whenever he serves a customer, he simply chooses the one who came to Berpizza first, and serves that customer.

On the other hand, Polycarp is an experienced waiter at Berpizza, and he knows which customers are going to spend a lot of money at the pizzeria (and which aren't) as soon as he sees them. For each customer, Polycarp estimates the amount of money this customer can spend, and when he serves a customer, he chooses the one that is expected to leave the most money at Berpizza (in case there are several such customers, he chooses the one who came first among them).

Obviously, no customer can be served twice, so Monocarp and Polycarp choose which customer to serve only among those who haven't been served yet.

When the number of customers gets really high, it becomes difficult for both Monocarp and Polycarp to choose the customer they are going to serve. Your task is to write a program that makes these choices for them. Formally, your program should be able to process three types of queries:

• $1$ $m$ — a customer comes to Berpizza, and Polycarp estimates the amount of money that they will spend as $m$;
• $2$ — Monocarp serves a customer which came to the pizzeria first;
• $3$ — Polycarp serves a customer which is expected to spend the largest amount of money at the pizzeria (if there are several such customers, the one that came to the pizzeria first is chosen).

For each query of types $2$ and $3$, report the number of the customer who was served (the customers are numbered in the order they come to the pizzeria, starting from $1$).

Monocarp 和 Polycarp 是位于 Bertown 市中心附近的披萨店 Berpizza 的两名服务员。由于他们的工作是为顾客提供服务，因此他们各自选择优先服务对象的方式不同。

营业日开始时，Berpizza 中没有顾客。顾客们会逐个到来。当一名顾客进入披萨店后，她会就座并等待 Monocarp 或 Polycarp 为其服务。Monocarp 在 Berpizza 工作仅两周，因此每当他服务一名顾客时，他总是选择最早到达 Berpizza 的那名顾客来服务。

另一方面，Polycarp 是 Berpizza 的资深服务员，他仅凭第一眼就能判断哪些顾客将在披萨店消费较多（哪些消费较少）。对每一名顾客，Polycarp 都会预估其可能的消费金额；而当他服务顾客时，他总是选择预计消费金额最高的那名顾客（若存在多名顾客预估消费金额相同，则从中选择最早到达的那一位）。

显然，任何顾客都不能被重复服务，因此 Monocarp 和 Polycarp 每次都只能在尚未被服务过的顾客中选择下一位服务对象。

当顾客数量变得非常庞大时，Monocarp 和 Polycarp 自行选择服务对象将变得十分困难。你的任务是编写一个程序，代替他们完成这些选择。形式化地说，你的程序应能处理以下三类查询：

• $1$ $m$ — 一名顾客来到 Berpizza，Polycarp 估计其消费金额为 $m$；
• $2$ — Monocarp 服务最早到达披萨店的顾客；
• $3$ — Polycarp 服务预计在披萨店消费金额最高的顾客（若存在多名顾客预估消费金额相同，则选择其中最早到达的那一位）。

对于每个类型为 $2$ 和 $3$ 的查询，请输出被服务顾客的编号（顾客按到达顺序编号，从 $1$ 开始）。

The first line contains one integer $q$ ($2 \le q \le 5 \cdot 10^5$) — the number of queries.

Then $q$ lines follow, each describing a query in one of the following formats:

• $1$ $m$ ($1 \le m \le 5 \cdot 10^5$) — a customer comes to Berpizza, and Polycarp estimates the amount of money that they will spend as $m$;
• $2$ — Monocarp serves a customer which came to the pizzeria first;
• $3$ — Polycarp serves a customer which is expected to spend the largest amount of money at the pizzeria (if there are multiple such customers, the one that came to the pizzeria first is chosen).

Queries of type $2$ and $3$ are asked only when there exists at least one customer that hasn't been served yet. There is at least one query of type $2$ or $3$ in the input.

第一行包含一个整数 $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$ 的查询。

For each query of type $2$ or $3$, print one integer — the number of the customer that has been served in that event. The customers are numbered in the order in which they come to the pizzeria, starting from $1$.

对于每个类型为 $2$ 或 $3$ 的查询，输出一个整数——即该事件中被服务的顾客编号。顾客按到达披萨店的顺序编号，从 $1$ 开始。