Min Stack

Problem statement

A monitoring console records readings on a stack. Besides undoing or inspecting the latest reading, the operator frequently asks for the smallest reading still present, so rescanning the stack on every query would be too slow. Your task Implement push x, pop, top and getMin. push adds x, pop removes the top, top returns the top value, and getMin returns the minimum stored value. Important details All operations must run in O(1) time. Queries and pop are issued only when the stack is nonempty. Duplicate minima must be handled: removing one copy does not remove another. Only top and getMin produce output. Worked example After push 4, push -2, getMin, pop, top, the answers are -2 and 4. Removing the latest reading restores 4 as the top.

Input format

First line: q. Next q lines contain operations.

Output format

Print one answer per top or getMin; print EMPTY if no operation produces output.

Constraints

1 <= q <= 30000; pushed values are signed 32-bit integers.

Sample input

5
push 4
push -2
getMin
pop
top

Sample output

-2
4