题目描述： 编程实现： 靶场上有$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$，表示靶场上靶的数量 第二行输入$n$个整数，分别表示从左到右每块靶上的数，整数之间以一个空格隔开

输出描述

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

4
3 2 4 6

120

提示

$1 \leq n \leq 300$

$1 \leq 整数 \leq 100$