Min Stack Implementation

You are required to implement a MinStack data structure that supports the following operations in O(1) time:

• push(val): Push an element onto the stack.
• pop(): Remove the top element from the stack.
• top(): Retrieve the element on the top of the stack.
• getMin(): Retrieve the minimum element currently in the stack.

The input will be a sequence of operations. It is guaranteed that the top and getMin operations are never called when the stack is empty. Your implementation should process each operation in constant time.

Note: All numbers are integers.

inputFormat

The input is read from stdin and has the following format:

 n
 op1
 op2
 ...
 opn

Where n is the number of operations, and each opi is one of the following commands:

• push x: Push the integer x onto the stack.
• pop: Remove the top element from the stack.
• top: Print the top element of the stack.
• getMin: Print the minimum element in the stack.

outputFormat

For every top and getMin operation in the input, output the corresponding result on a new line to stdout.## sample

6
push -2
push 0
push -3
getMin
pop
getMin

-3
-2