描述

编程实现：靶场上有n块靶排成一排，从左到右依次编号为1、2、3、…、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