Competitions
Stack Data Structure
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
First line contains number of operations n (1 ≤ n ≤ 106
). 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 (-109
≤ x ≤ 109
) - 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.
Input example #1
8 1 2 1 3 1 -3 3 2 3 2 3
Output example #1
-3 2 2