1746: 放飞汽球
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：18
Solved：8
Description
六一儿童节，学生们在少年宫大草坪上玩放飞汽球的游戏。每人有 n 个气球，每个汽球绳上有一数字，数字为 1 到 n，这些数字存放在数组 a 中。 要求你一个一个地放完所有的气球。放飞第 i 个气球，你可以获得 a[i - 1] * a[i] * a[i + 1] 块糖果。现在让你求出放飞完所有的 n个气球后，获得糖果的最大数量。
为了方便处理，我们对 a 数组稍作处理，将其数组的前后两边界各加上题目中假设存在的 a[0] 与 a[n+1] ，如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
Input
输入第一行一个整数 n。第二行为 n 个数字编号 ( 1~100 之间)，数字之间空一格。
Output
输出一个正整数，为获得糖果的最大数量。
Sample Input Copy
5
3 1 5 3 2
Sample Output Copy
87
HINT
2=<n<=100