e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Data Structures contest

Minimum in the stack

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.

prb4259.gif

Input

First line contains number of operations n (1n106). Next n lines contain the operations itself. The i-th line contains number ti - the type of operation (1 in the case of push operation, 2 in the case of pop, 3 if the operation demands to find minimum). In the case of push operation next goes integer x (-109x109) - element to be inserted into the structure. It is guaranteed that before each pop or getMin operation the structure is not empty.

Output

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

Time limit 3 seconds
Memory limit 128 MiB
Input example #1
8
1 2
1 3
1 -3
3
2
3
2
3
Output example #1
-3
2
2