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

说明

智能车的能源系统由一串环形排列的能量模块组成，每个模块都有 “输入功率标记” 和 “输出功率标记”（均为正整数），用于高效能量传输与回收。为满足不同工况下的能源需求，需将相邻模块通过能源转换器进行聚合，聚合过程会回收部分能量并生成新模块。

聚合规则如下：

相邻两个模块（A 和 B）可聚合：要求 A 的 “输出功率标记” 等于 B 的 “输入功率标记”（确保能量传输匹配）。 能量回收计算：若模块 A 的输入标记为 m、输出标记为 r，模块 B 的输入标记为 r、输出标记为 n，则聚合时回收的能量为 m * r * n（单位：毫焦）。
新模块生成：聚合后产生的新模块，输入标记为 A 的输入标记 m，输出标记为 B 的输出标记 n，可继续与相邻模块聚合。

由于模块呈环形排列（最后一个模块的输出标记等于第一个模块的输入标记），需通过能源转换器依次聚合相邻模块，直到系统中仅剩一个模块为止。不同的聚合顺序会导致总回收能量不同，请设计最优聚合顺序，使智能车从这串能量模块中回收的总能量最大。

例如：设能量模块数量 N=4，4 个模块的输入功率标记依次为 2、3、5、10（根据规则，模块 1 输出 = 3，模块 2 输出 = 5，模块 3 输出 = 10，模块 4 输出 = 2）。用记号⊕表示模块聚合操作，(j⊕k) 表示第 j、k 个模块聚合的回收能量：

第 4、1 个模块聚合的回收能量为：(4⊕1)=1023=60（毫焦）。
最优聚合顺序为 ((4⊕1)⊕2)⊕3，总回收能量为：1023 + 1035 + 10510 = 710（毫焦）。

输入格式

每组输入数据包含 2 行：
第 1 行：正整数 N（4≤N≤100），表示能量模块的个数。
第 2 行：N 个用空格隔开的正整数（均不超过 1000），第 i 个数为第 i 个模块的输入功率标记。
规则约束：当 i<N 时，第 i 个模块的 “输出功率标记” 等于第 i+1 个模块的 “输入功率标记”；第 N 个模块的 “输出功率标记” 等于第 1 个模块的 “输入功率标记”。

输出格式

每组输出仅 1 行，为一个正整数 E（E≤2.1×10⁹），表示最优聚合顺序下智能车回收的总能量（单位：毫焦）。

样例

4
2 3 5 10

710