该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

样例下载

题目描述

恰逢 H 国国庆，国王邀请 $n$ 位大臣来玩一个有奖游戏。首先，他让这 $n$ 位大臣排成一排，依次编号为 1 ~ n。然后，他让每个大臣在手上写下一个整数，编号为 i 的大臣写下的数是 ai。接下来，游戏开始：

每一次，国王会选择一位大臣让其出列，该大臣会获得国王奖赏的若干金币，具体数目是：该大臣自己手上的数乘以他左边的大臣的手上的数再乘以他右边的大臣的手上的数。如果出列的大臣的左边(或右边)没有大臣，那么在做乘法的时候对于没有大臣的那一边只需要乘以 1 就可以了。

当所有大臣都出列以后，游戏结束。

大臣出列的顺序不同，国王支付的金币个数就可能不同。

为了提前准备足够多的金币用于支付，国王想知道，他最多需要支付多少个金币？

输入

第一行：一个整数 n

第二行：n 个整数 ai

输出

一个整数，表示国王需要支付的最多金币个数。

样例输入

3
3 1 5

样例输出

35

样例解释

[ 3 1 5 ] ---中间大臣出列---> [ 3 5 ] ---左侧大臣出列---> [ 5 ] --剩余一个大臣出列---> [ ]

3×1×5 + 1×3×5 + 1×5×1 = 15 + 15 + 5 = 35

数据规模

30% 的数据：0 ≤ n ≤ 10, 0 ≤ ai ≤ 10

100% 的数据：0 ≤ n ≤ 500, 0 ≤ ai ≤ 100