题目描述

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

输出描述

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

样例

4
3 2 4 6

120

评分标准

10分：能正确输出第一组数据； 10分：能正确输出第二组数据； 10分：能正确输出第三组数据； 10分：能正确输出第四组数据； 10分：能正确输出第五组数据； 10分：能正确输出第六组数据； 10分：能正确输出第七组数据； 10分：能正确输出第八组数据； 10分：能正确输出第九组数据； 10分：能正确输出第十组数据。