Implementa una pila que, además de las operaciones de siempre, entregue su mínimo en \(O(1)\):

• push x: apila \(x\).
• pop: saca el elemento del tope (no imprime nada).
• top: imprime el elemento del tope.
• getMin: imprime el menor elemento de la pila.

Entrada

La primera línea tiene \(q\) \((1 \le q \le 10^5)\) y siguen \(q\) líneas con una operación cada una \((-2^{31} \le x \le 2^{31} - 1)\). pop, top y getMin solo aparecen con la pila no vacía.

Salida

Una línea por cada top y getMin, con lo que piden.

Ejemplo 1

Entrada

8
push -2
push 0
push -3
getMin
pop
top
getMin
pop

Salida

-3
0
-2

Ejemplo 2

Entrada

4
push 5
push 5
pop
getMin

Salida

5

Basado en el problema 155 de LeetCode, Min Stack, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.