Berpizza
Contest: 2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules)
Difficulty rating: 1400
Tags: data structures, implementation

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

Input format:
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.

Output format:
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$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Example input:
8
1 8
1 10
1 6
3
2
1 9
2
3

Example output:
2 1 3 4

Example input:
6
1 8
1 10
1 8
3
3
3

Example output:
2 1 3

Editorial:
The hardest part of this problem is to efficiently implement the third query, i. e. finding the customer with the greatest value of $$$m$$$ and erasing it. Simply iterating on all of them is too slow, since there may be up to $$$2.5 \cdot 10^5$$$ such queries and up to $$$5 \cdot 10^5$$$ customers at the pizzeria.
There are several solutions to this issue, I will describe two of them. The first solution is to treat each customer as a pair $$$(id, m)$$$, where $$$id$$$ is the number of the customer. Then the first query means "insert a new pair", the second query — "remove the pair with minimum $$$id$$$", and the third query — "remove the pair with maximum $$$m$$$". To maintain them, we can use two balanced binary trees that store these pairs — one will store them sorted by $$$id$$$, and the other — sorted by $$$m$$$. Then the second query means "find the leftmost element in the first tree and erase it from both trees", and the third query means "find the rightmost element in the second tree and erase it from both trees". Balanced binary trees can perform these operations in $$$O(\log n)$$$, where $$$n$$$ is the size of the tree. Note that in most languages you don't have to write a balanced binary tree from scratch — for example, the containers std::set in C++ and TreeSet in Java already support all of the required operations.
The second solution maintains three data structures: a queue for supporting the queries of type $$$2$$$, a heap for supporting the queries of type $$$3$$$, and an array or set that allows checking whether some customer was already deleted by a query. Finding the customer that came first using a queue or has a maximum value of $$$m$$$ using a heap is easy, but deleting some element from queue/heap is much harder (because we have to delete some arbitrary element, not necessarily the element at the head of the queue/heap). Instead, we can do it the other way: when we delete some customer from one of these data structures, we mark it as deleted. And while processing the following queries of type $$$2$$$ or $$$3$$$, we should check the element in the head of the data structure and, if it is marked as deleted, remove it before processing the query. Note that there can be multiple such elements, so it should be done in a loop. Since each element is deleted at most once, this solution works in $$$O(n \log n)$$$ amortized.