You are given a valid postfix (Reverse Polish) expression as a sequence of space-separated tokens. Each token is either an integer operand or one of the four operators +, -, *, /.
Evaluate the expression using a stack: on each operator, pop the two most recent values a (deeper) and b (on top), then push the result of a op b. Division / is integer division that truncates toward zero (for example 7 / 2 = 3 and -7 / 2 = -3).
The expression is guaranteed to be valid: exactly one value remains on the stack at the end, every operator has two operands available, and no division by zero occurs.
Input format
Line 1: an integer m, the number of tokens.
Line 2: m space-separated tokens forming the postfix expression. When m is 0 the expression is empty and the value is defined to be 0; the token line is present but empty.
Output format
A single integer: the value of the expression.
Constraints
- 0 ≤ m ≤ 100000
- Each operand is an integer with -1000000000 ≤ operand ≤ 1000000000.
- The expression is valid and never divides by zero.