Berpizza

题意翻译

初始时，有一个空的序列，接下来会有 $n$ 次操作。 你要构造程序，实现下面三种操作，每个操作首先用参数 $op$ 表示种类，具体的： - $op=1$ 时，再给定一个参数 $m$，你要向序列插入 $m$ 这个元素。 - $op=2$ 时，删除序列中最早插入的元素，输出被删除的这个元素是第几个被插入到序列的。 - $op=3$ 时，删除序列中数值最大的元素，输出被删除的这个元素是第几个被插入到序列的，特别的，如果有若干个元素都满足值最大这个要求，要删除的元素是最早被插入的元素。 $1\leq n\leq5\times10^5;1\leq m\leq5\times10^5;1\leq op\leq 3;$ 保证不会会出现序列为空时 $op=2$ 或 $op=3$ 的情况。

题目描述

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 $ ).

输入输出格式

输入格式

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.

输出格式

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 $ .

输入输出样例

输入样例 #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