Design a Stack that Supports getMin() in O(1) Time

Implement a special stack that supports push, pop, peek, and an additional operation getMin() to return the minimum element in constant time.

Input