Min Stack

Build a stack that also returns its minimum element in O(1):

• push x — push x
• pop — remove the top element (print nothing)
• top — print the top element
• getMin — print the smallest element currently in the stack

Input:

• line 1: q
• next q lines: one operation each. pop, top and getMin are only used when the stack is not empty.

Output: one line for every top and getMin.

Constraints: 1 ≤ q ≤ 10⁵, −2³¹ ≤ x ≤ 2³¹ − 1.

The trick: store, next to every value, the minimum of the stack at the moment it was pushed. Popping then automatically restores the previous minimum. Scanning the whole stack on every getMin is O(n) — too slow for the big tests.