编程实现

靶场上有$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\le n\le 300)$，表示靶场上靶的数量 第二行输入$n$个整数($1\le 整数 \le 100)$，分别表示从左到右每个靶上的数，整数之间以一个空格隔开

输出描述

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

样例

输入样例 #1

4
3 2 4 6

输出样例 #1

120