Description

M Shipping Company needs to analyze the flow of goods in and out of its warehouses. The only records they have are logs tracking container entries and exits. The log contains two types of operations: the first type is an entry operation along with the container’s weight; the second type is an exit operation. All records are strictly in chronological order. The rule for entries and exits is last-in, first-out (LIFO), meaning each exit operation removes the most recently entered container currently in the warehouse.

For analysis purposes, analysts randomly inserted a third type of operation — a query operation — into the log. When analyzing the log, whenever a query operation is encountered, you must report the maximum container weight currently in the warehouse.

Input Format

Contains $N+1$ lines:

The first line is a positive integer $N$, which is the total number of operations in the log.

The next $N$ lines are each in one of the following three formats:

• Format 1: 0 X, indicating an entry operation; the positive integer $X$ is the weight of the container being stored.
• Format 2: 1, indicating an exit operation; the most recently entered container (at that moment) exits.
• Format 3: 2, indicating a query operation; the program must output the maximum container weight currently in the warehouse.

When the warehouse is empty, you should ignore a pop operation. When querying an empty warehouse, you should output $0$.

Output Format

The number of output lines equals the number of query operations in the log. Each line contains one integer, which is the query result.

13
0 1
0 2
2
0 4
0 2
2
1
2
1
1
2
1
2

2
4
4
1
0

Hint

Constraints

• For $20\%$ of the testdata, $N \le 10$.
• For $40\%$ of the testdata, $N \le 1000$.
• For $100\%$ of the testdata, $1 \le N \le 200000$, $1 \le X \le 10^8$.

Translated by ChatGPT 5