StackDesign
Design a stack that supports push, pop, top and retrieving the minimum element, all in O(1) time. You are given a list of operations to run: push x, pop, top (report the top element) and getMin (report the smallest element currently in the stack).
Input
Line 1: q, the number of operations. Next q lines: push x, pop, top or getMin.
Output
For each top and getMin print the value on its own line. Operations are always valid (never applied to an empty stack).
Constraints
1 <= q <= 10^4 -10^4 <= x <= 10^4
Example 1
Input
6 push 3 push 1 push 2 getMin pop getMin
Output
1 1
The minimum is 1 both times; popping 2 does not change it.