魔法种子

题目背景

“1zhiO2” 不仅是一位星空牧羊者，还是一位技艺精湛的草药学家——“羊”神农。在它的魔法花园里，有一排整齐的培育槽，专门用来种植具备“魔力共鸣”效应的特殊种子。

1zhiO2 手中有 $N$ 枚独一无二的魔法种子，每一枚都蕴含着不同的魔力值。当两枚种子被种在相邻的培育槽时，它们会相互共鸣，产生一股强大的魔法能量。这股能量的大小，恰好等于两枚种子魔力值的乘积。

为了准备一场盛大的魔法仪式，1zhiO2 计划将这 $N$ 枚种子全部种入花园里那仅有的 $N$ 个培育槽中。它想知道，如何安排这些种子的种植顺序，才能使得花园里产生的总魔法能量最强？

给定 $N$ 枚魔法种子，第 $i$ 枚种子的魔力值为 $a_i$ 。

你需要将这 $N$ 枚种子不重不漏地种入一排共 $N$ 个的培育槽中。定义一种种植方案的总魔法能量为所有相邻种子对的魔力值乘积之和。

例如，如果一种种植方案的种子魔力值顺序为 $p_1, p_2, \dots, p_N$ ，那么产生的总魔法能量为：

E = \sum_{i=1}^{N-1} p_i \times p_{i+1}

你的任务是，找到一种排列方式，使得总魔法能量 $E$ 最大，并输出这个最大值。

输入第一行包含一个正整数 $N$ ，表示种子的数量。

输入第二行包含 $N$ 个正整数 $a_1, a_2, \dots, a_N$ ，用空格分隔，表示每枚种子的魔力值。

输出一行，包含一个整数，表示可以产生的最大总魔法能量。

3
3 5 8

对于魔力值为 {3, 5, 8} 的三枚种子，最优的排列方式之一是 5, 8, 3 (或其翻转 3, 8, 5)。

对于排列 5, 8, 3，总能量 = $5 \times 8 + 8 \times 3 = 40 + 24 = 64$ 。
其他排列方式，例如 3, 5, 8，总能量 = $3 \times 5 + 5 \times 8 = 15 + 40 = 55$ ，不如前者。可以证明，64 是所有排列中能产生的最大总能量。

子任务编号	$N$ 的范围	$a_i$ 的范围
1	$2 \le N \le 10$	$1 \le a_i \le 1000$
2	$2 \le N \le 2 \cdot 10^5$	$1 \le a_i \le 1000$

在下列比赛中: