描述

打气球是游乐场里的经典项目，最近一个新开的游乐场也不例外，他们的游戏规则如下：

1. 气球排成一排，每个气球上标有一个正整数，代表这个气球的分数。
2. 玩家用玩具枪打气球，每打破一个气球，可以得到一个分数，这个分数等于这个气球和与它相邻的气球的分数的乘积。
3. 打破全部气球后，游戏结束。

请你编写程序，对于给定的一排气球，可以得到的最高分是多少。

例如，对于三个气球3，3，2，最高分的打法是，先打中间的气球，得到3x3x2=18分，再打右边的气球，得到3x2=6分，最后打剩下的，得到3分，最高分是18+6+3=27。

输入输出格式

输入

两行，第一行一个正整数n（1<=n<=1000），代表气球的总数；第二行n个正整数，代表每个气球的分数，其顺序就是气球的摆放顺序。

输出

输出一个整数，代表可以打出的最高分数。

样例

3
3 3 2

27

4
3 2 5 2

69