880088 - 打靶

通过次数

0

提交次数

0

Time Limit : 1 秒
Memory Limit : 128 MB

靶场上有n块靶排成一排,从左到右依次编号为1、2、3、….n,且每块靶上都标有一个整数。 当某块靶被击中后,击中者会得到 x y z 的积分。( y 表示被击中的靶上的数, ×表示其左侧最近且未被击中的靶上的数,z表示其右侧最近且未被击中的靶上的数。 如果其左侧不存在未被击中的靶,则x为1;如果其右侧不存在未被击中的靶,则z为1。) 计算完积分后,这块靶就会退出靶场(不在这排靶中)。 请计算击中所有靶后能得到的最高积分是多少?

例如:n=4,表示有4块靶,这4块靶上的数从左到右分别是3、2、4、6; 按照下列顺序打靶,可以得到最高积分: 1.打2号靶,得到的积分是24(324); 2.打3号靶,得到的积分是72(346); 3.打1号靶,得到的积分是18(136); 4.打4号靶,得到的积分是6(161); 最终获得的积分是120(24+72+18+6)。

Input

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

Output

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

Examples

Input

4
3 2 4 6

Output

120