eolymp
bolt
Try our new interface for solving problems
Problems

Minimum in the stack

Minimum in the stack

Time limit 3 seconds
Memory limit 128 MiB

Implement a data structure with the next operations:

  1. Push x to the end of the structure.

  2. Pop the last element from the structure.

  3. Print the minimum element in the structure.

Input data

The first line contains the number of operations n\:(1 \le n \le 10^6). Each of the next n lines contains one operation. The i-th line contains the number t_i — the type of operation:

  • 1 in the case of a push operation;

  • 2 in the case of a pop operation;

  • 3 if the operation asks to find minimum;

In the case of a push operation, next comes the integer x\:(-10^9 \le x \le 10^9) — element to be inserted into the structure. It is guaranteed that before each pop or getMin operation the structure is not empty.

Output data

For each getMin operation, print on a separate line one number — the minimal element in the structure.

Examples

Input example #1
8
1 2
1 3
1 -3
3
2
3
2
3
Output example #1
-3
2
2