En notación polaca inversa los operadores van después de sus operandos: 3 4 + es \(3 + 4\) y 2 1 + 3 * es \((2 + 1) \cdot 3\). Evalúa la expresión dada.

Los operadores son +, -, * y /. La división es entera y trunca hacia cero (\(-7 / 2 = -3\)).

Entrada

La primera línea tiene la cantidad de tokens \(k\) \((1 \le k \le 10^5)\) y la segunda los \(k\) tokens: números enteros \((|x| \le 200)\) u operadores. La expresión es válida, nunca se divide por \(0\) y todos los resultados intermedios cumplen \(|v| \le 2^{31} - 1\).

Salida

El valor de la expresión.

Ejemplo 1

Entrada

5
2 1 + 3 *

Salida

9

Ejemplo 2

Entrada

5
4 13 5 / +

Salida

6

Ejemplo 3

Entrada

13
10 6 9 3 + -11 * / * 17 + 5 +

Salida

22

Basado en el problema 150 de LeetCode, Evaluate Reverse Polish Notation, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.