题目描述

靶场上有n块靶排成一排，从左到右依次编号为1、2、3、…、n，每块靶上都标有一个整数。 当某块靶被击中后，击中者会得到 x * y * z 的积分：

• y 表示被击中的靶上的数字
• x 表示其左侧最近且未被击中的靶上的数字，若左侧无未被击中的靶则x为1
• z 表示其右侧最近且未被击中的靶上的数字，若右侧无未被击中的靶则z为1

击中靶后该靶会退出靶场，请求出击中所有靶后能获得的最高积分。

示例说明

当n=4，靶上数字从左到右为3、2、4、6时，最优打靶顺序如下：

1. 击中2号靶，积分 3*2*4=24
2. 击中3号靶，积分 3*4*6=72
3. 击中1号靶，积分 1*3*6=18
4. 击中4号靶，积分 1*6*1=6 总积分 24+72+18+6=120

输入描述

1. 第一行输入整数n（1 ≤ n ≤ 300），表示靶的数量
2. 第二行输入n个整数（1 ≤ 整数 ≤ 100），表示从左到右每块靶上的数字，整数间用空格隔开

输出描述

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

样例输入

4
3 2 4 6

样例输出

120