题目描述

靶场上有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），分别表示从左到右每块靶上的积分，整数之间以一个空格隔开

输出描述

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

样例数据1

输入

4
3 2 4 6

输出

120

样例数据2

输入

8
98 97 96 96 99 90 95 99

输出

5523210

程序运行限制

时间限制：1000ms、内存限制：64MB