Background

打靶的最高得分

题目描述： 靶场上有 n 块靶排成一排，从左到右依次编号为 1、2、3、...、n，且每块靶上都标有一个整数。当某块靶被击中后，击中者会得到 x * y * z 的积分。（y 表示被击中的靶上的数，x 表示其左侧最近且未被击中的靶上的数，z 表示其右侧最近且未被击中的靶上的数。如果其左侧不存在未被击中的靶，则 x为 1；如果其右侧不存在未被击中的靶，则 z 为 1。）

计算完积分后，这块靶就会退出靶场（不在这排靶中）。

请计算击中所有靶后能得到的最高积分是多少？

例如：n = 4，表示有 4 块靶，这 4 块靶上的数从左到右分别是 3、2、4、6；按照下列顺序打靶，可以得到最高积分：

打 2 号靶，得到的积分是 24（3 * 2 * 4）；

打 3 号靶，得到的积分是 72（3 * 4 * 6）；

打 1 号靶，得到的积分是 18（1 * 3 * 6）；

打 4 号靶，得到的积分是 6（1 * 6 * 1）；

最终获得的积分是 120（24 + 72 + 18 + 6）。

输入描述：

第一行输入一个整数 n（1≤n≤300），表示靶场上靶的数量 第二行输入 n 个整数（1≤整数≤100），分别表示从左到右每个靶上的数，整数之间以一个空格隔开输出描述：

输出一个整数，表示击中所有靶后能得到的最高积分

样例输入：

4

3 2 4 6

样例输出：

120#

评分标准：

10分：能正确输出第一组数据； 10分：能正确输出第二组数据； 10分：能正确输出第三组数据； 10分：能正确输出第四组数据； 10分：能正确输出第五组数据； 10分：能正确输出第六组数据； 10分：能正确输出第七组数据； 10分：能正确输出第八组数据； 10分：能正确输出第九组数据； 10分：能正确输出第十组数据。

Limitation

1s, 1024KiB for each test case.