题目描述

靶场上有 $n$ 块靶排成一排，从左到右依次编号为 $1,2,3,\cdots,n$，且每块靶上都标有一个整数。

当某块靶被击中后，击中者会得到 $x * y * z$ 的积分。($y$ 表示被击中的靶上的数，$x$ 表示其左侧最近且未被击中的靶上的数，$z$ 表示其右侧最近且未被击中的靶上的数。如果其左侧不存在未被击中的靶，则 $x$ 为 $1$；如果其右侧不存在未被击中的靶，则 $z$ 为 $1$。）

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

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

例如：$n = 4$，表示有 $4$ 块靶，这 $4$ 块靶上的数从左到右分别是 $3、2、4、6$;

按照下列顺序打靶，可以得到最高积分：

1. 打 $2$ 号靶，得到的积分是 $24(3*2*4)$；
2. 打 $3$ 号靶，得到的积分是 $72(3* 4 * 6)$；
3. 打 $1$ 号靶，得到的积分是 $18(1* 3 * 6)$；
4. 打 $4$ 号靶，得到的积分是 $6(1* 6* 1)$；

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

输入格式

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

输出格式

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

4
3 2 4 6

120

Hint

【数据范围】 对于 $20\%$ 的数据，$1\le n \le 10$ 对于 $100\%$ 的数据，$1\le n \le 300$。