题目描述

有 $n$ 个气球，编号为 $0$ 到 $n - 1$，每个气球上都标有一个数字，这些数字存在数组 $ nums$ 中。

现在要求你戳破所有的气球。戳破第 $ i$ 个气球，你可以获得 $nums[i - 1] * nums[i] * nums[i + 1]$ 枚硬币。 这里的 $i - 1$ 和 $ i + 1$ 代表和 $ i$ 相邻的两个气球的序号。如果 $i - 1$或 $i + 1$ 超出了数组的边界，那么就当它是一个数字为 $1$ 的气球。

求所能获得硬币的最大数量。

输入格式

输入的第一行包含 $N$ ，之后给出由 $N$ 个数字组成的序列 $nums$。

输出格式

一个整数，为所能获得硬币的最大数量。

样例输入输出

样例输入

4
3 1 5 8

样例输出

167

数据范围

对于$100%$ 的数据保证 $1 <= N <= 300$，$0 <= nums[i] <= 100$。