SDE Path

Implement a Min Stack

Medium

Implement a Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in O(1).

Input format

The first line contains Q. Each of the next Q lines is one of: push x, pop, top, getMin. All pop/top/getMin calls occur on a non-empty stack.

Output format

For each top print the top value and for each getMin print the current minimum, one per line. All operations must be O(1).

Constraints

  • Values fit in a 64-bit signed integer
  • Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

Sample cases

Example 1
Input
14
push 29
getMin
push -1
push 31
push 28
pop
push -4
push 21
top
pop
top
push 7
push -4
pop
Expected output
29
21
-4
Example 2
Input
13
push 30
getMin
getMin
getMin
getMin
getMin
getMin
getMin
getMin
getMin
push 47
top
getMin
Expected output
30
30
30
30
30
30
30
30
30
47
30