题面描述

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

她决定按某一种顺序吃完这 $n$ 颗糖果。
如果当前吃的糖果美味值为 $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)$

输出

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

输入输出样例 #1

输入

3
1 2 3

输出

23

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