C. 美味糖果

传统题

1000ms

256MiB

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

题面描述

小青有 $n$ 颗糖果，第 $i$ 颗糖果的基础美味值为 $a_i$ 。

她决定按某一种顺序吃完这 $n$ 颗糖果。
如果当前吃的糖果美味值为 $a_i$ ，上一颗吃的糖果美味值为 $a_{i-1}$ ，那么这一次额外获得的美味值为：

(a_i-a_{i-1})^2 + 2(a_i+a_{i-1})

第一颗糖果没有上一颗糖果，因此 第一颗糖果不会产生额外美味值。

请你帮助小青安排一种吃糖果的顺序，使得获得的 总额外美味值最大，并输出这个最大值。

第一行输入一个整数 $n$ 。 $(1\leq n \leq 8)$
第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$ 。 $(1\leq a_i \leq 10^3)$

输出一个整数，表示最大的总额外美味值。

输入

3
1 2 3

输出

样例解释吃的顺序为2-3-1的时候，最大获得的额外美味值为 $(3-2)*(3-2)+2*(3+2) + (3-1)*(3-1)+2*(3+1)=23$