有 n 个气球排列在一排，每个气球上都有一个数字，存储在数组 nums 中。
当你戳破某个气球 i 时，你将获得硬币数为：

  coins = nums[left] × nums[i] × nums[right]

其中，left 和 right 分别是 i 左右两侧最近未被戳破的气球的下标；如果某一侧没有气球，则视该位置的数字为 1。

请你设计一个策略，使得最后戳破所有气球后获得的硬币总数最大。

提示： 为了方便处理边界情况，可以在原数组两端各补一个 1，这样最终计算的是在扩展数组中的最优解。

• 第一行包含一个整数 n (1 ≤ n ≤ 500)，表示气球的个数。
• 第二行包含 n 个整数，表示数组 nums，每个数字均在 [0, 100] 范围内。

• 输出一个整数，表示可以获得的最大硬币数。

数据范围

• 1 ≤ n ≤ 500
• 0 ≤ nums[i] ≤ 100

样例

样例 1

输入：

4
3 1 5 8

输出：

167

说明：
扩展数组为 [1, 3, 1, 5, 8, 1]。
一种最优策略如下（顺序不唯一）：

• 第一次戳破气球 1（即原数组中数字 1）：获得 1×3×1 = 3
• 第二次戳破气球 3（数字 5）：获得 1×5×8 = 40
• 第三次戳破气球 2（数字 1）：获得 3×1×8 = 24
• 最后戳破剩下的气球（数字 8）：获得 1×8×1 = 8
  （实际过程较为复杂，经过动态规划计算后，最大硬币数为 167。）

样例 2

输入：

1
7

输出：

7

说明：
当只有 1 个气球时，扩展数组为 [1, 7, 1]。
戳破唯一的气球可获得：1×7×1 = 7。

区间dp