后缀表达式求值

题目描述

给定一个合法的后缀表达式，计算它的值。

表达式由非负整数和 +、-、* 三种运算符组成，所有记号之间用空格分隔。

后缀表达式的计算规则：

• 遇到数字：压栈；
• 遇到运算符：弹出两个数，先弹出的是右操作数，后弹出的是左操作数，计算后把结果压回栈。

输入格式

第一行一个整数 $n$，表示记号个数。

第二行给出 $n$ 个记号。

输出格式

输出表达式的值。

数据范围

$1\le n\le 100000$，保证表达式合法，所有中间结果在 long long 范围内。

样例输入

5
3 4 + 2 *

样例输出

14