Minimum in the stack
Minimum in the stack
Implement a data structure with the next operations:
Push x to the end of the structure.
Pop the last element from the structure.
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
8 1 2 1 3 1 -3 3 2 3 2 3
-3 2 2